Search in Rotated Sorted Array with duplicates allowed. It looks like a one-line change and it is not: duplicates break the single assumption the original solution rests on, and the honest consequence is that the worst case stops being logarithmic. Being able to say why — rather than patching until the tests pass — is the whole point of the problem.
The problem
An ascending sorted array, possibly containing duplicates, has been rotated at some unknown pivot. Given a target, return whether it is present. Return a boolean, not an index — with duplicates there may be several correct indices.
[2,5,6,0,0,1,2] target 0 -> true
[2,5,6,0,0,1,2] target 3 -> false
[1,0,1,1,1] target 0 -> true the case that breaks the naive version
[1,1,1,1,1] target 2 -> false nothing to learn from any comparison
[1] target 1 -> trueWhat problem 33 relied on
The original works because of one guarantee: at least one half of the array is always
sorted, and you can tell which by a single comparison. Compare nums[lo] to
nums[mid]; if the left is not descending, the left half is the sorted one, otherwise
the right is. Then check whether the target falls inside the sorted half's range, and discard half
the array either way.
Duplicates destroy the comparison, not the guarantee. One half is still sorted — it just becomes impossible to work out which:
[1, 0, 1, 1, 1] lo=0 mid=2 hi=4
^ ^ ^
1 1 1 nums[lo] == nums[mid] == nums[hi]
[1, 1, 1, 0, 1] same three values, pivot on the other side
^ ^ ^
1 1 1Two arrays with the pivot in different halves present identical evidence at every point the algorithm is allowed to look. No comparison can distinguish them, so no decision made from those three values can be right for both. This is an information argument, not an implementation problem, and it is worth stating in exactly those terms.
The only safe move
When nums[lo] == nums[mid] == nums[hi], you cannot discard a half. What you
can do is discard the two endpoints, because they are equal to nums[mid], which
you have already tested against the target:
lo++; hi--;That is safe — the discarded values are known not to be the target — and it makes progress, so the loop terminates. It just makes progress of two elements instead of half the array, which is where the complexity goes.
Note the condition needs all three to be equal. If nums[lo] == nums[mid] but
nums[hi] differs, there is still enough information to identify the sorted half, and
shrinking would throw away a working binary step.
Java
class Solution {
public boolean search(int[] nums, int target) {
int lo = 0, hi = nums.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] == target) return true;
if (nums[lo] == nums[mid] && nums[mid] == nums[hi]) {
// Ambiguous: both halves look identical from here. The ends are
// equal to nums[mid], which is already known not to be the target.
lo++;
hi--;
} else if (nums[lo] <= nums[mid]) { // left half is sorted
if (nums[lo] <= target && target < nums[mid]) {
hi = mid - 1;
} else {
lo = mid + 1;
}
} else { // right half is sorted
if (nums[mid] < target && target <= nums[hi]) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
}
return false;
}
}The range tests use the sorted half's endpoints, and the inclusivity is not decorative.
nums[lo] <= target && target < nums[mid] is closed on the left and open on
the right because nums[mid] was already checked and rejected. Getting these backwards
produces a solution that works on most inputs and loops forever on a few.
lo + (hi - lo) / 2 rather than (lo + hi) / 2, for the overflow reason
that Sqrt(x) goes into.
Python
class Solution:
def search(self, nums: list[int], target: int) -> bool:
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return True
if nums[lo] == nums[mid] == nums[hi]:
lo += 1 # ambiguous: shrink both ends
hi -= 1
elif nums[lo] <= nums[mid]: # left half is sorted
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
else: # right half is sorted
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return FalsePython's chained comparisons make both the ambiguity test and the range tests read like the
mathematical statements they are — nums[lo] == nums[mid] == nums[hi] and
nums[lo] <= target < nums[mid]. This is one of the places where the Python version
is genuinely clearer rather than just shorter.
Complexity
| Case | Time | Space |
|---|---|---|
| Few duplicates | O(log n) | O(1) |
| Worst case | O(n) | O(1) |
[1,1,1,...,1,0,1,...,1] forces the ambiguous branch almost every iteration, so the
search degenerates to a linear scan — and that is not a weakness of this particular algorithm.
Distinguishing that array from an all-ones array requires finding the single 0, and no algorithm can
do that without inspecting Ω(n) elements in the worst case. The lower bound is on the
problem.
Say that when asked "can you do better?". The answer is no, with a reason, which is a much better answer than trying.
What changes from problem 33
| 33 | 81 | |
|---|---|---|
| Returns | an index | a boolean — several indices could be right |
| Sorted half | always identifiable | sometimes ambiguous |
| Worst case | O(log n) | O(n) |
Find Minimum in Rotated Sorted Array II (154) is the same degradation applied to a different question, and it fails in the same place for the same reason. Recognising the shared cause across both is worth more than solving either.
What the interviewer is checking
- That you start from problem 33's invariant and identify precisely what duplicates break.
- That the ambiguity needs all three of
lo,mid,hiequal. - That shrinking both ends is safe, and why.
- That you volunteer the
O(n)worst case rather than claimingO(log n). - That the
O(n)bound is inherent, not a flaw in your approach. - The inclusive/exclusive boundaries in the range tests.
[1,0,1,1,1]and an all-equal array.