Search in Rotated Sorted Array
Search for a target value in an array that has been rotated at an unknown pivot.
Problem Understanding
A sorted array (e.g., [0, 1, 2, 4, 5, 6, 7]) is rotated at some pivot.
- Example Rotation:
[4, 5, 6, 7, 0, 1, 2].
Given this rotated array and a target target, return the index of target. If not found, return -1.
The search has to run in O(log n) time, so a straight scan through the array is not enough.
Examples
- ([4,5,6,7,0,1,2]), target = 0 -> Index 4.
- ([4,5,6,7,0,1,2]), target = 3 -> -1.
Attempt 1: Brute Force
Simply iterate through the array and look for the target.
for(let i=0; i<nums.length; i++) {
if (nums[i] === target) return i;
}
return -1;
Complexity: O(n).
This is trivial but violates the O(log n) requirement.
The Intuition: Half is always sorted
Even though the array is rotated, at any split (midpoint), at least one half must be sorted.
Consider [4, 5, 6, 7, 0, 1, 2]:
- Mid at index 3 (Value 7).
- Left part
[4, 5, 6, 7]is sorted (4 <= 7). - Right part
[7, 0, 1, 2]is NOT sorted.
- Left part
We can use this property:
- Identify which half is sorted.
- Check if the
targetlies within that sorted half's range. - If yes, search that half.
- If no, search the other half.
Interactive Visualization
Observe how the algorithm decides which half to search based on the sorted property.
Dry Run
Array: [4, 5, 6, 7, 0, 1, 2], Target 0.
| Step | L | H | Mid | Val | Sorted Half? | Logic | Action |
|---|---|---|---|---|---|---|---|
| 1 | 0 | 6 | 3 | 7 | Left [0..3]=4..7? Yes. | Is 0 in [4, 7]? No. | Search Right side. L=Mid+1=4 |
| 2 | 4 | 6 | 5 | 1 | Left [4..5]=0..1? Yes. | Is 0 in [0, 1]? Yes. | Search Left side. H=Mid-1=4 |
| 3 | 4 | 4 | 4 | 0 | - | 0 == 0. Found! | Return 4 |
The Solution Template
Standard Rotated Search logic.
Search in Rotated Sorted Array Code
1/**2 * @param {number[]} nums3 * @param {number} target4 * @return {number}5 */6var search = function(nums, target) {7 let left = 0;8 let right = nums.length - 1;910 while (left <= right) {11 let mid = Math.floor(left + (right - left) / 2);1213 if (nums[mid] === target) return mid;1415 if (nums[left] <= nums[mid]) {16 if (nums[left] <= target && target < nums[mid]) {17 right = mid - 1;18 } else {19 left = mid + 1;20 }21 } else {22 if (nums[mid] < target && target <= nums[right]) {23 left = mid + 1;24 } else {25 right = mid - 1;26 }27 }28 }29 return -1;30};
Edge Cases
- Duplicate values: This specific logic fails with duplicates (e.g., [1,0,1,1,1]). Handling them needs an extra step that skips equal values, and the worst case degrades to O(n).
- Not rotated: Works as standard binary search.
- Target at pivot: Handled.
Summary
By checking which half is sorted, we can safely eliminate half the search space even if the array is rotated.