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.
- 1 <= nums.length <= 5000
- -10⁴ <= nums[i] <= 10⁴
- nums is guaranteed to be rotated at some pivot.
- -10⁴ <= target <= 10⁴
Intuition
Search in rotated sorted array ii adds duplicates to the rotated-search problem, and that single change costs the logarithmic guarantee.
The original works by determining which half is sorted — comparing nums[left] with nums[mid] — then checking whether the target lies within that sorted half. Exactly one half is always sorted, so the choice is unambiguous.
Duplicates break the comparison:
- When nums[left], nums[mid], and nums[right] are all equal, neither half can be identified as sorted, and no comparison at those positions distinguishes the cases.
Consider [1, 1, 1, 0, 1] and [1, 0, 1, 1, 1]. Both have equal values at the three probe positions, yet the rotation point sits in different halves.
The standard resolution is to shrink the range by one from each end when that ambiguity appears: left++ and right--. It is safe because the duplicated values at the ends are also present at mid, so discarding them cannot remove the only copy of the target.
That step is what costs the bound. An array of identical values reduces by two per iteration, giving O(n) worst case — and this is unavoidable, not an implementation flaw.
The other branches are unchanged. If the left half is sorted, check whether the target falls within it; otherwise the right half is sorted and the same test applies there.
This problem returns a boolean, not an index — a small difference from the original that is easy to overlook.
Average performance stays near O(log n) when duplicates are sparse.
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
Before reading on: price up what the direct approach costs here, then ask what property lets you throw away half the range after one comparison. Aim for O(n) worst case, O(log n) average time and O(1) space.
Recall the original's mechanism
Compare nums[left] with nums[mid] to find which half is sorted, then test whether the target lies inside it. Exactly one half is always sorted.
Identify what duplicates break
When the left, mid, and right values are all equal, neither half can be identified. [1,1,1,0,1] and [1,0,1,1,1] probe identically but rotate differently.
Shrink both ends on ambiguity
Apply left++ and right--. Safe because those values also appear at mid, so no unique copy of the target is discarded.
Keep the two decisive branches
If the left half is sorted, check whether the target lies within it; otherwise the right half is sorted and the same test applies.
Accept the linear worst case
An array of identical values shrinks by two per iteration, giving O(n). This degradation is inherent, not an implementation flaw.
Return a boolean
This problem returns whether the target exists, not its index — a small difference from the original that is easy to miss.
Cost of the search
O(log n) average with sparse duplicates, degrading to O(n) worst case. Space stays O(1).
Solution & live demo
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.