Search in Rotated Sorted Array II
Search in Rotated Sorted Array II is a medium binary search problem solved with the rotated array pattern.
The best approach, optimal (sorted-half search with tie shrinking), runs in O(log n) average, O(n) worst time and O(1) space.
Below are 2 approaches in Java, from linear scan up.
Problem
A sorted array that may contain duplicates was rotated at an unknown pivot. Return whether target is in the array.
Examples
Example 1
- Input
nums = [2, 5, 6, 0, 0, 1, 2], target = 0- Output
true
Example 2
- Input
nums = [1, 0, 1, 1, 1], target = 0- Output
true- Why
- Here nums[lo] == nums[mid] == nums[hi], so you cannot tell which half is sorted.
Constraints
1 <= nums.length <= 5000; duplicates allowed.- Return true or false.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.
| Approach | Time | Space |
|---|---|---|
| Linear scan | O(n) | O(1) |
| Optimal (sorted-half search with tie shrinking) | O(log n) average, O(n) worst | O(1) |
1Linear scan
O(n)O(1)Check every element.
- Return true if any element equals target.
class Solution {
public boolean search(int[] nums, int target) {
for (int x : nums) if (x == target) return true;
return false;
}
}2Optimal (sorted-half search with tie shrinking)
O(log n) average, O(n) worstO(1)Same as the distinct version, but when nums[lo] == nums[mid] == nums[hi] the sorted half is ambiguous. Neither end is the target (mid was just checked), so lo++ and hi--.
- If nums[mid] == target, return true.
- If nums[lo] == nums[mid] && nums[mid] == nums[hi]: lo++, hi--; continue.
- Otherwise apply the sorted-half rule.
class Solution {
public boolean search(int[] nums, int target) {
int lo = 0, hi = nums.length - 1;
while (lo <= hi) {
int mid = (lo + hi) >>> 1;
if (nums[mid] == target) return true;
if (nums[lo] == nums[mid] && nums[mid] == nums[hi]) { lo++; hi--; continue; }
if (nums[lo] <= nums[mid]) {
if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
else lo = mid + 1;
} else {
if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
else hi = mid - 1;
}
}
return false;
}
}Edge cases to test
- nums[lo] == nums[mid] == nums[hi]
- All values equal
Hints
Hint 1
When the three ends are equal, shrink both ends by one and try again.
FAQ
What is the best time complexity for Search in Rotated Sorted Array II?
Optimal (sorted-half search with tie shrinking) runs in O(log n) average, O(n) worst time and O(1) extra space.
Which pattern does Search in Rotated Sorted Array II use?
It is a binary search problem that uses the rotated array pattern. Other problems with the same pattern: Find How Many Times Array is Rotated, Find Minimum in Rotated Sorted Array, Find Minimum in Rotated Sorted Array II.
Is there a brute force solution for Search in Rotated Sorted Array II?
Yes. Linear scan takes O(n) time and O(1) space. Check every element.
Which edge cases should I test for Search in Rotated Sorted Array II?
nums[lo] == nums[mid] == nums[hi]; All values equal.