# 81. 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, but `nums` may contain duplicates. Would this affect the runtime complexity? How and why?

## 解法解析

### 解法範例

#### 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

``````/**
* @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

``````
``````

#### 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

``````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

``````
``````

#### Swift

``````
``````