Search in Rotated Sorted Array
At every step, one half is still sorted — decide which, then whether the target lies in it.
Binary Search Trace
Problem
Given a strictly increasing array that was rotated around one unknown pivot, return the index of a target value. Return -1 when the target does not appear. Design the search to remain logarithmic despite the rotation.
Examples
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
0 is at index 4. The left side of the first midpoint is sorted, but 0 is outside its range, so the search moves right.Input: nums = [6,7,1,2,3,4,5], target = 8
Output: -1
8.The Goal
A sorted array of distinct numbers has been rotated at some unknown index. Return the index of target, or -1, in O(log n) time.
For nums = [4, 5, 6, 7, 0, 1, 2] and target = 0, the answer is 4.
The whole array isn't sorted, so plain binary search can steer the wrong way. But one half of any range always is.
One half is always sorted
Split a rotated array anywhere, and at least one side has no drop in it. Its first and last numbers bound everything inside.
Use the sorted half to decide where the target can be.
Key Idea: Find the Sorted Half
At each middle, compare nums[lo] with nums[mid]. If nums[lo] <= nums[mid], the left half is sorted. Otherwise the drop is in the left half, so the right half is sorted.
A sorted half holds the target only if the target falls between its two ends. If it does, keep that half. If not, the target can only be in the other one.
If nums[mid] is the target, return mid.
nums[4] = 0
The Algorithm
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if nums[mid] == target:
return mid
if nums[lo] <= nums[mid]:
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
else:
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1Use <= in nums[lo] <= nums[mid]. When lo and mid are the same index, the left half is that one number, and it's sorted.
| Approach | Time | How |
|---|---|---|
| Sorted-half search | O(log n) | Drop the half that can't hold the target |
| Find the drop, then search one side | O(log n) | Two binary searches |
| Scan | O(n) | Ignores the order |
Walkthrough
Run it on [4, 5, 6, 7, 0, 1, 2] with target = 0.
The middle is 7. The left half, 4 to 7, is sorted and doesn't include 0, so lo = 4. The next middle is 1. Its left half, 0 to 1, is sorted and does include 0, so hi = 4. The middle is now index 4, holding 0: return 4.
Change k on the stage to rotate the array somewhere else.
Checkpoint · predict the next step
Step 4 of 9 on the stage: 0 isn't in 4 to 7, so it can only be right of mid. lo = 4.
lo on 0 (index 4) · hi on 2 (index 6) · target 0
Pitfalls
- Find the sorted half before comparing the target with
nums[mid]. At the first middle, 0 is less than 7, but 0 is to the right. - Test the range against the sorted half's ends, with the right mix of
<and<=:nums[lo] <= target < nums[mid]. - Repeated numbers break the sorted-half test:
nums[lo] == nums[mid]no longer says which side is sorted. - An array that isn't rotated still works. Its left half is always sorted.
nums = [4, 5, 6, 7, 0, 1, 2], the target is 0, and mid is at 7. Where does the search go?
Complexity
Each step keeps one half and drops the other, so it takes O(log n) steps. It keeps three indices, so extra space is O(1).
Each step does a fixed amount of work: one comparison to find the sorted half, and one range test.
One half dropped each step
- StepsOne half dropped each time.dominantO(log n)
- Each stepFind the sorted half, test the range.O(1)
- Boundslo, hi and mid.O(1)
| n | 10 | 100 | 1,000 | 10,000 |
|---|---|---|---|---|
| O(log n) | 3 | 7 | 10 | 13 |
| O(n) | 10 | 100 | 1K | 10K |
Rotation costs nothing: one half is always sorted.
In short
Binary search as usual, but first determine which side of mid is sorted (compare nums[lo] to nums[mid]). If the target falls within that sorted side's range, search there; otherwise search the other half. The rotation never breaks the halving.
Common mistake
Assuming the whole array is monotonic — you must check which half is sorted before choosing a direction.