# 81. Search in Rotated Sorted Array II

### Leetcode

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

&#x20;

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

### 解答 <a href="#ti-jie" id="ti-jie"></a>

* **方法一**

基本上是利用與 33 題 [方法二](https://bcjohnblue.gitbook.io/leetcode/33.-search-in-rotated-sorted-array#ti-jie) 同樣的解法，但會有一個額外的問題，那就是 nums 裡的值可能會是重複的，所以會導致以下兩種狀況用 33 題的方式無法求解。

For example:

nums = \[1,0,1,1,1,1,1,1,1,1], target = 0&#x20;

nums = \[1,1,1,1,1,1,1,1,1,0,1], target = 0

第一輪 binary search 後找到中間的值 = 1，但以上兩種狀況，0 有可能出現在左邊或右邊，無法判別接著要往哪個方向進行 binary search。所以對於 nums\[mid] 與 nums\[0] 相同的情況下，需要再對左右都個別執行 binary search

```
var search = function(nums, target) {
    if(target === nums[0]) return true;

    const binarySearch = (low, high) => {
      while(low < high) {
          // console.log(low, high)
          const mid = Math.floor((low + high) / 2);
          if(nums[mid] === target) return true;
          if(nums[mid] > nums[0]) {
              if(target > nums[0]) {
                  if(target > nums[mid]) low = mid + 1;
                  else high = mid;
              } else {
                  low = mid + 1;                
              }
          } else if(nums[mid] < nums[0]) {
              if(target > nums[0]) high = mid;
              else {
                  if(target > nums[mid]) low = mid + 1;
                  else high = mid;
              }
          } else {
            // nums[mid] === nums[0] 的狀況下，往左右都進行尋找
            return binarySearch(mid+1, high) || binarySearch(low, mid);
          }
      }
      return target === nums[low];
    }
    
    return binarySearch(0, nums.length - 1)
};
```

Runtime: 72 ms, faster than 91.81% of JavaScript online submissions for Search in Rotated Sorted Array II.

Memory Usage: 40.4 MB, less than 33.92% of JavaScript online submissions for Search in Rotated Sorted Array II.

### 測資

```
let nums = [2,5,6,0,0,1,2], target = 0; // true
nums = [2,5,6,0,0,1,2], target = 3; // false
nums = [1,0,1,1,1,1,1,1,1,1], target = 0; // true
nums = [1,1,1,1,1,1,1,1,1,0,1], target = 0; // true

console.log(search(nums, target))
```
