Search in Rotated Sorted Array II
Given a sorted array nums that was rotated at some pivot and may contain duplicates, return true if target is in the array, or false otherwise.
Intuition
In the version without duplicates, you can always tell which half of a rotated array is sorted by comparing nums[mid] with nums[left]. Duplicates break that: when nums[left] == nums[mid] == nums[right], you cannot tell which side the rotation falls on. The fix is to shrink the window by one whenever this ambiguity arises — left += 1 (or right -= 1). This costs at most O(n) in the worst case (all identical elements), but on average the search is still logarithmic. Outside that edge case, the standard rotated-array binary search applies: identify the sorted half, check if the target lies within it, and discard the other half.
The signal is 'binary search in a rotated sorted array, but with duplicates'. The no-duplicate version always distinguishes the sorted half; duplicates add one edge case where the comparison is inconclusive and you must fall back to linear shrinking. Any sorted-but-rotated search with possible repeats follows this pattern.
Approach
Start with standard binary search boundaries
Set left = 0 and right = len(nums) - 1. Loop while left <= right, computing mid = (left + right) // 2. If nums[mid] == target, return True.
Handle the ambiguous case: `nums[left] == nums[mid]`
When nums[left] == nums[mid], you cannot tell whether the left half is sorted or whether the rotation is hiding in it. The safe move is left += 1 — discard one element and try again. This is the only place duplicates add cost compared to the no-duplicates version.
Identify the sorted half and narrow the search
If nums[left] <= nums[mid], the left half [left, mid] is sorted. Check if target falls in [nums[left], nums[mid]) — if so, search left; otherwise search right. If nums[left] > nums[mid], the right half [mid, right] is sorted. Check if target falls in (nums[mid], nums[right]] — if so, search right; otherwise search left. Time is O(n) worst case, O(log n) average.
Return `False` if the loop ends without finding the target
If the entire range is exhausted, the target does not exist in the array.
Solution
Common pitfalls
Not handling the ambiguous duplicate case at all
if nums[left] <= nums[mid]:
# assume left half is sortedif nums[left] == nums[mid]:
left += 1
continue
if nums[left] <= nums[mid]:When nums[left] == nums[mid], the left half might not be sorted — the rotation could be hidden inside it. Skipping this check routes the search the wrong way, causing false negatives on arrays like [1,1,3,1].
Using strict < instead of <= when checking the sorted half
if nums[left] < nums[mid]:
if nums[left] <= nums[mid]:
When left == mid (a two-element window), nums[left] == nums[mid] is trivially true and the left 'half' is a single element — still sorted. Using strict < falls through to the wrong branch and misroutes the search.
Decrementing right in the ambiguous case instead of incrementing left
if nums[left] == nums[mid]:
right -= 1if nums[left] == nums[mid]:
left += 1Both directions are technically valid for resolving ambiguity, but the rest of the algorithm compares against nums[left] to identify the sorted half. Shrinking from the left keeps the comparison consistent. Shrinking from the right can work if the subsequent comparisons are adjusted, but mixing them is a source of bugs.
Edge cases
[2,2,2,2,2] and target = 3The ambiguous case triggers every iteration, shrinking by one each time. The search degrades to O(n), but correctly returns False.
The left half is always sorted, and the standard binary search path works normally.
The sorted-half check routes the search to the correct side; nums[mid] == target catches it.