Question

81. Search in Rotated Sorted Array II

中文文档

Description

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
• -104 <= nums[i] <= 104
• nums is guaranteed to be rotated at some pivot.
• -104 <= target <= 104

 

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?

Solutions

Solution 1: Binary Search

We define the left boundary $l=0$ and the right boundary $r=n-1$ for the binary search, where $n$ is the length of the array.

During each binary search process, we get the current midpoint $mid=(l+r)/2$.

• If $nums[mid] \gt nums[r]$, it means that $[l,mid]$ is ordered. At this time, if $nums[l] \le target \le nums[mid]$, it means that $target$ is in $[l,mid]$, otherwise $target$ is in $[mid+1,r]$.
• If $nums[mid] \lt nums[r]$, it means that $[mid+1,r]$ is ordered. At this time, if $nums[mid] \lt target \le nums[r]$, it means that $target$ is in $[mid+1,r]$, otherwise $target$ is in $[l,mid]$.
• If $nums[mid] = nums[r]$, it means that the elements $nums[mid]$ and $nums[r]$ are equal. At this time, we cannot determine which interval $target$ is in, so we can only decrease $r$ by $1$.

After the binary search ends, if $nums[l] = target$, it means that the target value $target$ exists in the array, otherwise it means it does not exist.

The time complexity is approximately $O(\log n)$, and the space complexity is $O(1)$. Here, $n$ is the length of the array.

class Solution:
  def search(self, nums: List[int], target: int) -> bool:
    n = len(nums)
    l, r = 0, n - 1
    while l < r:
      mid = (l + r) >> 1
      if nums[mid] > nums[r]:
        if nums[l] <= target <= nums[mid]:
          r = mid
        else:
          l = mid + 1
      elif nums[mid] < nums[r]:
        if nums[mid] < target <= nums[r]:
          l = mid + 1
        else:
          r = mid
      else:
        r -= 1
    return nums[l] == target

class Solution {
  public boolean search(int[] nums, int target) {
    int l = 0, r = nums.length - 1;
    while (l < r) {
      int mid = (l + r) >> 1;
      if (nums[mid] > nums[r]) {
        if (nums[l] <= target && target <= nums[mid]) {
          r = mid;
        } else {
          l = mid + 1;
        }
      } else if (nums[mid] < nums[r]) {
        if (nums[mid] < target && target <= nums[r]) {
          l = mid + 1;
        } else {
          r = mid;
        }
      } else {
        --r;
      }
    }
    return nums[l] == target;
  }
}

class Solution {
public:
  bool search(vector<int>& nums, int target) {
    int l = 0, r = nums.size() - 1;
    while (l < r) {
      int mid = (l + r) >> 1;
      if (nums[mid] > nums[r]) {
        if (nums[l] <= target && target <= nums[mid]) {
          r = mid;
        } else {
          l = mid + 1;
        }
      } else if (nums[mid] < nums[r]) {
        if (nums[mid] < target && target <= nums[r]) {
          l = mid + 1;
        } else {
          r = mid;
        }
      } else {
        --r;
      }
    }
    return nums[l] == target;
  }
};

func search(nums []int, target int) bool {
  l, r := 0, len(nums)-1
  for l < r {
    mid := (l + r) >> 1
    if nums[mid] > nums[r] {
      if nums[l] <= target && target <= nums[mid] {
        r = mid
      } else {
        l = mid + 1
      }
    } else if nums[mid] < nums[r] {
      if nums[mid] < target && target <= nums[r] {
        l = mid + 1
      } else {
        r = mid
      }
    } else {
      r--
    }
  }
  return nums[l] == target
}

function search(nums: number[], target: number): boolean {
  let [l, r] = [0, nums.length - 1];
  while (l < r) {
    const mid = (l + r) >> 1;
    if (nums[mid] > nums[r]) {
      if (nums[l] <= target && target <= nums[mid]) {
        r = mid;
      } else {
        l = mid + 1;
      }
    } else if (nums[mid] < nums[r]) {
      if (nums[mid] < target && target <= nums[r]) {
        l = mid + 1;
      } else {
        r = mid;
      }
    } else {
      --r;
    }
  }
  return nums[l] === target;
}