Search in Rotated Sorted Array II
Decide whether a target is in a rotated sorted array that may contain duplicates, with binary search plus a shrink step when duplicates hide the sorted half.
Problem Understanding
Search in Rotated Sorted Array II: a non-decreasing array (duplicates allowed) was rotated at an unknown pivot. Return true if target is in it, false otherwise. Make the search as fast as you can.
Examples: [2,5,6,0,0,1,2], target 0 → true; target 3 → false.
The Intuition: One Extra Case for Ties
Start from Search in Rotated Sorted Array: at every step one half of [left, right] is sorted, so check whether the target falls inside that half's range and keep or drop it.
Duplicates break exactly one thing:
- If
nums[left] == nums[mid] == nums[right], the sorted half cannot be identified. - But those ends are not the target (they equal
nums[mid], already checked), so drop both and continue. - Every other step is the normal rotated binary search.
The same tie problem appears in Find Minimum in Rotated Sorted Array II; compare with the distinct case in Find Minimum in Rotated Sorted Array.
Interactive Walkthrough
TARGET 2
READY
L
0
1
2
3
4
R
5
Left
0
Mid
:
Right
5
Sorted half
:
Is 2 in the rotated array? left = 0, right = 5
Next
mid = 2, and nums[2] = 1
Array
Target
L, M and R stay on every step, the sorted half is outlined, and cells outside the range are struck out. Try Hidden dip to see a shrink reveal which half is sorted.
Dry Run Table
Input: [1,0,1,1,1], target 0.
| left | mid | right | What happens |
|---|---|---|---|
| 0 | 2 | 4 | 1, 1, 1 all equal: shrink |
| 1 | 2 | 3 | nums[1] = 0 ≤ 1: left half [1..2] sorted, 0 in [0, 1): right = 1 |
| 1 | 1 | 1 | nums[1] = 0: found |
Answer: true.
The Solution Template
The rotated binary search with one added branch.
Search in Rotated Sorted Array II Code
1var search = function(nums, target) {2 let left = 0, right = nums.length - 1;3 while (left <= right) {4 const mid = (left + right) >> 1;5 if (nums[mid] === target) return true;6 if (nums[left] === nums[mid] && nums[mid] === nums[right]) {7 left++;8 right--;9 } else if (nums[left] <= nums[mid]) {10 if (nums[left] <= target && target < nums[mid]) right = mid - 1;11 else left = mid + 1;12 } else {13 if (nums[mid] < target && target <= nums[right]) left = mid + 1;14 else right = mid - 1;15 }16 }17 return false;18};
Edge Cases & Common Mistakes
- Checking only
nums[left] == nums[mid]: shrinking just the left end also works, but you must not decide a half is sorted on a tie. - Shrinking before checking mid: compare
nums[mid]with the target first, or you might drop the target. - All elements equal: the shrink runs until the range is empty; O(n).
- No rotation: the array is simply sorted and the left half is always sorted.
- Returning an index: this problem returns a boolean.
Summary
Rotated binary search, plus: when nums[left], nums[mid] and nums[right] are equal, move both ends inward. O(log n) on typical inputs, O(n) in the worst case, O(1) space.
More practice: DSA interview questions with answers · patterns cheat sheet