81. Search in Rotated Sorted Array II
You are given an integer array nums that started out sorted in non-decreasing order and was then rotated at some pivot you don't know. Unlike the classic version of this problem, values may repeat. Given nums and an integer target, return true if target occurs anywhere in the array and false otherwise.
Duplicates can disguise the pivot: in [1, 0, 1, 1, 1] the endpoints and the middle all read 1, so a single comparison can't tell you which half is the sorted one. Aim to beat a plain linear scan on average, while accepting that duplicates make a linear worst case unavoidable.
Example 1:
Input: nums = [2, 5, 6, 0, 0, 1, 2], target = 0
Output: true
Explanation: The value 0 sits at indices 3 and 4, so the answer is true.
Example 2:
Input: nums = [2, 5, 6, 0, 0, 1, 2], target = 3
Output: false
Explanation: No element of the array equals 3.
Constraints:
- 1 ≤ nums.length ≤ 5000
- -10⁴ ≤ nums[i] ≤ 10⁴
- nums is a non-decreasing array rotated at some pivot (possibly by 0 positions)
- -10⁴ ≤ target ≤ 10⁴
Hints:
Forget the structure for a second: a straight scan already answers the question in O(n). The rotation is only useful if you can exploit it to skip work.
In the duplicate-free version, comparing nums[mid] with nums[lo] tells you which half is sorted, and you keep whichever half could contain the target. When can that comparison lie to you here?
The only ambiguous case is nums[lo] == nums[mid] == nums[hi]. In that situation it is always safe to shrink both ends inward by one — you can never step over the target that way. Every other case binary-searches exactly like the no-duplicates problem.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [2, 5, 6, 0, 0, 1, 2], target = 0
Expected output: true