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.

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

解答

• 方法一

基本上是利用與 33 題 方法二 同樣的解法，但會有一個額外的問題，那就是 nums 裡的值可能會是重複的，所以會導致以下兩種狀況用 33 題的方式無法求解。

For example:

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

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