Intuition
Rotated binary search normally checks which half is sorted by comparing nums[mid] to nums[left]. Duplicates break that test when nums[left] == nums[mid] == nums[right] — you can't tell which side is sorted, so shrink both ends by one and retry.
Explanation
Rotated binary search, plus a duplicate escape hatch
In a rotated sorted array at least one half [left..mid] or [mid..right] is fully sorted. Compare nums[mid] with nums[left] to find the sorted half, then check whether target lies inside it to decide which way to go.
The duplicate problem: when nums[left] == nums[mid] == nums[right], the comparison can't tell which half is sorted (e.g. [1,1,1,0,1]). The safe fix is to simply drop both ends by one (left++, right--) and continue — this is the only case that degrades toward O(n).
while left <= right:
mid = (left + right) // 2
if nums[mid] == target: return True
if nums[left] == nums[mid] == nums[right]: left++; right-- # ambiguous
elif nums[left] <= nums[mid]: # left half sorted
if nums[left] <= target < nums[mid]: right = mid-1
else: left = mid+1
else: # right half sorted
if nums[mid] < target <= nums[right]: left = mid+1
else: right = mid-1
return False
Worked example
nums = [2, 5, 6, 0, 0, 1, 2], target = 0.
l=0, r=6, mid=3→nums[3]=0 == target→ return true.
For target = 3 the search would keep splitting and never find it → false.
Complexity
- Time: O(log n) average; O(n) worst case when many duplicates force the shrink step.
- Space: O(1).
Implementation
class Solution {
public boolean search(int[] nums, int target) {
int l = 0, r = nums.length - 1;
while (l <= r) {
int m = (l + r) / 2;
if (nums[m] == target) return true;
if (nums[l] == nums[m] && nums[m] == nums[r]) {
l++;
r--;
} else if (nums[l] <= nums[m]) { // left half sorted
if (nums[l] <= target && target < nums[m]) r = m - 1;
else l = m + 1;
} else { // right half sorted
if (nums[m] < target && target <= nums[r]) l = m + 1;
else r = m - 1;
}
}
return false;
}
}