Duplicates change everything in rotated array binary search. What was a clean O(log n) algorithm becomes O(n) in the worst case. The elegant "one half is always sorted" property becomes ambiguous.
But here's the good news: understanding why duplicates break the pattern helps you handle them correctly. This guide will show you the exact scenario that breaks, how to fix it, and when the worst case occurs.
The problem: When arr[left] == arr[mid] == arr[right], we can't determine which half is sorted.
The fix: Shrink the search space by incrementing left and decrementing right.
The cost: Worst case becomes O(n) instead of O(log n).
Modified template:
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
return True
# Handle duplicates
if arr[left] == arr[mid] == arr[right]:
left += 1
right -= 1
elif arr[left] <= arr[mid]:
# Left half sorted
if arr[left] <= target < arr[mid]:
right = mid - 1
else:
left = mid + 1
else:
# Right half sorted
if arr[mid] < target <= arr[right]:
left = mid + 1
else:
right = mid - 1
return FalseWithout duplicates: We can always determine which half is sorted by comparing arr[left] with arr[mid].
With duplicates: When arr[left] == arr[mid], we can't tell which half is sorted.
Array: [1, 0, 1, 1, 1], target = 0
left=0, right=4, mid=2
arr[0]=1, arr[2]=1, arr[4]=1
Is left half sorted?
arr[left]=1 <= arr[mid]=1 ✓
But left half is [1, 0, 1] → NOT sorted!
Is right half sorted?
We can't tell from arr[left] vs arr[mid]
Right half is [1, 1, 1] → Sorted
The comparison arr[left] <= arr[mid] doesn't tell us which half is sorted!The key insight: When arr[left] == arr[mid], there are two possibilities:
Possibility 1: Left half is sorted (all elements equal)
Array: [1, 1, 1, 1, 0, 1]
↑ ↑
left mid
Left half: [1, 1, 1, 1] → Sorted (all equal)Possibility 2: Left half is NOT sorted (has rotation)
Array: [1, 0, 1, 1, 1, 1]
↑ ↑
left mid
Left half: [1, 0, 1, 1] → NOT sorted (has break at 1→0)We can't distinguish between these cases by just comparing arr[left] with arr[mid].
Worst case: Almost all elements are the same, with one different element.
Array: [1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1]
↑
Only different element
At almost every step:
arr[left] == arr[mid] == arr[right] = 1
We can't eliminate half the array
We must shrink by 1 element at a time
Result: O(n) time complexityArray: [2, 2, 2, 2, 2, 2, 2, 0, 2], target = 0
Iteration 1:
left=0, right=8, mid=4
arr[0]=2, arr[4]=2, arr[8]=2
Can't determine which half is sorted
→ left=1, right=7
Iteration 2:
left=1, right=7, mid=4
arr[1]=2, arr[4]=2, arr[7]=0
arr[left] != arr[right], can proceed normally
arr[1]=2 <= arr[4]=2 → left half sorted
2 <= 0 < 2? No → search right
→ left=5
Iteration 3:
left=5, right=7, mid=6
arr[6]=2 != 0
arr[5]=2 <= arr[6]=2 → left half sorted
2 <= 0 < 2? No → search right
→ left=7
Iteration 4:
left=7, right=7
arr[7]=0 == 0 → Found!
Total iterations: 4 (but we only eliminated 1 element in iteration 1)def search(nums: List[int], target: int) -> bool:
"""
Search in rotated sorted array with duplicates
Time: O(log n) average, O(n) worst case
Space: O(1)
"""
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return True
# Handle duplicates: when we can't determine which half is sorted
if nums[left] == nums[mid] == nums[right]:
left += 1
right -= 1
elif nums[left] <= nums[mid]:
# Left half is sorted
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
# Right half is sorted
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return FalseWhen arr[left] == arr[mid] == arr[right]:
arr[left] and arr[right] are not the target (since arr[mid] != target)left += 1, right -= 1This is safe because:
left or right (they equal mid, which != target)Some implementations only shrink one side:
if nums[left] == nums[mid]:
left += 1
elif nums[left] <= nums[mid]:
# Left half sorted
...This also works but may be slightly slower (shrinks by 1 instead of 2 per iteration).
When: No duplicates, or duplicates don't cause ambiguity
Array: [4, 5, 6, 7, 0, 1, 2]
No duplicates → always can determine sorted half
→ O(log n)When: Few duplicates, ambiguity is rare
Array: [2, 5, 6, 0, 0, 1, 2]
Occasional duplicates → usually can determine sorted half
→ O(log n) on averageWhen: Almost all elements are duplicates
Array: [1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1]
Almost always arr[left] == arr[mid] == arr[right]
→ Must shrink by 1 each time
→ O(n)| Array Type | Time Complexity |
|---|---|
| No duplicates | O(log n) |
| Few duplicates | O(log n) average |
| Many duplicates | O(n) worst case |
When:
Template:
if nums[left] <= nums[mid]:
# Left half sorted
...
else:
# Right half sorted
...When:
Template:
if nums[left] == nums[mid] == nums[right]:
left += 1
right -= 1
elif nums[left] <= nums[mid]:
# Left half sorted
...
else:
# Right half sorted
...def search(nums: List[int], target: int) -> bool:
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return True
if nums[left] == nums[mid] == nums[right]:
left += 1
right -= 1
elif nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return False
# Examples
print(search([2, 5, 6, 0, 0, 1, 2], 0)) # True
print(search([2, 5, 6, 0, 0, 1, 2], 3)) # False
print(search([1, 1, 1, 1, 1, 1, 1, 0, 1], 0)) # Truedef findMin(nums: List[int]) -> int:
"""
Find minimum in rotated sorted array with duplicates
Time: O(log n) average, O(n) worst case
"""
left, right = 0, len(nums) - 1
while left < right:
mid = left + (right - left) // 2
if nums[mid] > nums[right]:
# Minimum is in right half
left = mid + 1
elif nums[mid] < nums[right]:
# Minimum is in left half or at mid
right = mid
else:
# nums[mid] == nums[right], can't determine
# Shrink search space
right -= 1
return nums[left]
# Examples
print(findMin([2, 2, 2, 0, 1])) # 0
print(findMin([1, 3, 5])) # 1
print(findMin([2, 2, 2, 2, 2])) # 2❌ Wrong:
# Using standard template on array with duplicates
if nums[left] <= nums[mid]:
# This doesn't work when nums[left] == nums[mid] but left half is not sorted✅ Correct:
if nums[left] == nums[mid] == nums[right]:
left += 1
right -= 1
elif nums[left] <= nums[mid]:
...❌ Wrong:
"Binary search is always O(log n)"✅ Correct:
"Binary search on rotated array with duplicates is O(log n) average, O(n) worst case"❌ Wrong:
if nums[left] == nums[mid]: # Not enough
left += 1✅ Correct:
if nums[left] == nums[mid] == nums[right]: # Check all three
left += 1
right -= 1Q: Why does the worst case become O(n)?
A: When almost all elements are the same, we can't eliminate half the array. We must shrink by 1 element at a time, leading to O(n).
Q: Can I avoid the O(n) worst case?
A: No, not with binary search. The ambiguity is fundamental. If you need guaranteed O(log n), the array must not have duplicates.
Q: Should I always use the duplicate-handling template?
A: Only if the problem allows duplicates. For problems guaranteeing unique elements, use the standard template (it's simpler).
Q: What if I only check nums[left] == nums[mid]?
A: This works but is less efficient. Checking all three (left, mid, right) lets you shrink both sides.
Q: Is there a better algorithm for duplicates?
A: Not for worst case. Linear search is O(n) always. Binary search is O(log n) average, O(n) worst case. Average case is better.
Duplicates break the elegant "one half is always sorted" property of rotated array binary search. When arr[left] == arr[mid] == arr[right], we can't determine which half is sorted.
Key takeaways:
left and decrementing rightThe modified template:
if nums[left] == nums[mid] == nums[right]:
left += 1
right -= 1
elif nums[left] <= nums[mid]:
# Standard logic
...Use this template when:
For arrays without duplicates, use the standard template for guaranteed O(log n). For more details, see Rotated Sorted Array Guide, Rotated Array Proof, and the Complete Binary Search Guide.
Next time you see duplicates in a rotated array, remember: handle the ambiguous case by shrinking the search space.
LeetCopilot is a free browser extension that enhances your LeetCode practice with AI-powered hints, personalized study notes, and realistic mock interviews — all designed to accelerate your coding interview preparation.
Also compatible with Edge, Brave, and Opera
Add to Chrome for free