Search in Rotated Sorted Array II
MediumDuplicates blur the sorted half
Same as searching a rotated list, but skip equal values at the ends that hide which half is sorted.
The idea
With duplicates, a[lo] == a[mid] == a[hi] hides which half is sorted — shrink both ends by one and continue; otherwise it's the same rotated search.
2
5
6
0
0
1
2
0
1
2
3
4
5
6
target0
Step 1 of 5. Brute force: walk left to right until you find 0. Values: 2, 5, 6, 0, 0, 1, 2. target 0.
1/5
Brute force
timeO(n)spaceO(1)
Scan one by one.
1for (let i = 0; i < n; i++)2 if (nums[i] === target) return true;3return false;Input
- array
- [2, 5, 6, 0, 0, 1, 2]
Memory
- i
- —
- target
- 0
- checked
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- nums = [2, 5, 6, 0, 0, 1, 2], target = 0
- Output:
- true
- Explanation:
- 0 is present.
Example 2
- Input:
- nums = [2, 5, 6, 0, 0, 1, 2], target = 3
- Output:
- false
- Explanation:
- 3 is missing → false.
Example 3
- Input:
- nums = [1, 0, 1, 1, 1], target = 0
- Output:
- true
- Explanation:
- Duplicates need a careful edge shrink.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.