Search in Rotated Sorted Array II

Description

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).

You are given a target value to search. If found in the array return true, otherwise return false.

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

Follow up:

• This is a follow up problem to Search in Rotated Sorted Array, where nums may contain duplicates.
• Would this affect the run-time complexity? How and why?

Solution(javascript)

// 去掉右边的部分，找到分割点然后二分
// 类似的题 33 154
const search = (nums = [], target) => {
  let left = 0
  let right = nums.length - 1
  let pivot = 0
  while (nums[right] === nums[0] && left <= right) {
    right -= 1
  }
  while (left <= right) {
    const middle = Math.floor((left + right) / 2)
    if (nums[middle] > nums[middle + 1]) {
      pivot = middle
      break
    } else if (nums[middle] < nums[middle - 1]) {
      pivot = middle - 1
      break
    } else if (nums[middle] >= nums[0]) {
      left = middle + 1
    } else {
      right = middle - 1
    }
  }
  const binarySearch = (low, high) => {
    while (low <= high) {
      const middle = Math.floor((low + high) / 2)
      if (nums[middle] === target) {
        return true
      }
      if (nums[middle] < target) {
        low = middle + 1
      } else {
        high = middle - 1
      }
    }
    return false
  }

  const inLeft = binarySearch(0, pivot)

  return inLeft || binarySearch(pivot + 1, nums.length - 1)
}