Find a Value in a Rotated Sorted Array That May Contain Duplicates
Implement searchRotatedWithDuplicates
This is a follow-up to searching a rotated sorted array, except
nums may now contain duplicate values. Given the rotated array nums and an integer target, return true if target is present, or false otherwise.
Duplicates mean nums[lo], nums[mid], and nums[hi] can all tie, making it impossible to tell which half is sorted — when that happens, shrink both ends inward by one and try again. This pushes the worst case to O(n), but the algorithm still behaves like binary search whenever the tie doesn't occur.
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
Example 3:
Input: nums = [3,1,2,3,3,3,3], target = 1
Output: true
+ 4 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ nums.length ≤ 5000 - ●
-10⁴ ≤ nums[i] ≤ 10⁴ - ●
nums was sorted in non-decreasing order, then rotated at some unknown pivot - ●
nums may contain duplicate values - ●
-10⁴ ≤ target ≤ 10⁴
nums =
[2, 5, 6, 0, 0, 1, 2]
target =
0