# LeetCode Solution, Medium, 81. Search in Rotated Sorted Array II

# [81. Search in Rotated Sorted Array II](https://leetcode.com/problems/search-in-rotated-sorted-array-ii/)

## 題目敘述

There is an integer array nums sorted in non-decreasing order (not necessarily with **distinct** values).

Before being passed to your function, `nums` is **rotated** at an unknown pivot index `k` (`0 <= k < nums.length`) such that the resulting array is `[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]` (**0-indexed**). For example, `[0,1,2,4,4,4,5,6,6,7]` might be rotated at pivot index `5` and become `[4,5,6,6,7,0,1,2,4,4]`.

Given the array `nums` **after** the rotation and an integer `target`, return _`true` if `target` is in `nums`, or `false` if it is not in `nums`_.

You must decrease the overall operation steps as much as possible.

**Example 1:**

    Input: nums = [2,5,6,0,0,1,2], target = 0
    Output: true

**Example 2:**

    Input: nums = [2,5,6,0,0,1,2], target = 3
    Output: false

**Constraints:**

- `1 <= nums.length <= 5000`
- `-10**4 <= nums[i] <= 10**4`
- `nums` is guaranteed to be rotated at some pivot.
- `-10**4 <= target <= 10**4`

**Follow up:** This problem is similar to [Search in Rotated Sorted Array](https://leetcode.com/problems/search-in-rotated-sorted-array/description/), but `nums` may contain **duplicates**. Would this affect the runtime complexity? How and why?

### 題目翻譯

今天有一個排序過的陣列 `nums`，但會被挪移。在這挪移過後的陣列中找是不是含有 `target` 存在。如果存在就回傳 `true`，沒有就回傳 `false`。

## 解法解析

這題是使用 Binary Search，但要注意的是其開頭和結尾是切開來的。細節的話可以看看官網本身的講解，我覺得滿清楚的 - [Solution](https://leetcode.com/problems/search-in-rotated-sorted-array-ii/solution/)

### 解法範例

#### Go

```go
func search(nums []int, target int) bool {
	n := len(nums)
	if n == 0 {
		return false
	}

	end, start := n-1, 0
	for start <= end {
		mid := (start + end) / 2
		if nums[mid] == target {
			return true
		}
		if nums[start] == nums[mid] {
			start += 1
			continue
		}

		if nums[mid] > nums[start] {
			if nums[mid] > target && target >= nums[start] {
				end = mid - 1
			} else {
				start = mid + 1
			}
		} else {
			if target > nums[mid] && nums[end] >= target {
				start = mid + 1
			} else {
				end = mid - 1
			}
		}
	}

	return false
}
```

#### JavaScript

```javascript
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {boolean}
 */
var search = function (nums, target) {
    const n = nums.length;
    if (n === 0) return false;

    let end = n - 1,
        start = 0;

    while (start <= end) {
        let mid = Math.floor((start + end) / 2);
        if (nums[mid] === target) return true;
        if (nums[start] === nums[mid]) {
            start++;
            continue;
        }

        if (nums[mid] > nums[start]) {
            if (nums[mid] > target && target >= nums[start]) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        } else {
            if (target > nums[mid] && nums[end] >= target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
    }

    return false;
};
```

#### Kotlin

```kotlin
```

#### PHP

```php
class Solution
{

    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Boolean
     */
    function search($nums, $target)
    {
        $n = count($nums);
        if ($n == 0) {
            return false;
        }
        $end = $n - 1;
        $start = 0;
        while ($start <= $end) {
            $mid = intdiv($start + $end, 2);
            if ($nums[$mid] == $target) {
                return true;
            }
            if ($nums[$start] == $nums[$mid]) {
                $start++;
                continue;
            }

            if ($nums[$mid] > $nums[$start]) {
                if ($nums[$mid] > $target && $target >= $nums[$start]) {
                    $end = $mid - 1;
                } else {
                    $start = $mid + 1;
                }
            } else {
                if ($target > $nums[$mid] && $nums[$end] >= $target) {
                    $start = $mid + 1;
                } else {
                    $end = $mid - 1;
                }
            }
        }
        return false;
    }
}
```

#### Python

```python
class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        n = len(nums)
        if n == 0:
            return False
        end = n - 1
        start = 0
        while start <= end:
            mid = (start + end) // 2

            if nums[mid] == target:
                return True

            if nums[start] == nums[mid]:
                start += 1
                continue

            pivot_array = nums[start] <= nums[mid]
            if pivot_array ^ (nums[start] <= target):
                if pivot_array:
                    start = mid + 1
                else:
                    end = mid - 1
            else:
                if nums[mid] < target:
                    start = mid + 1
                else:
                    end = mid - 1
        return False
```

#### Rust

```rust
```

#### Swift

```swift
```