Search in Rotated Sorted Array
How to keep binary search's O(log n) speed even after a sorted list has been cut and rotated, so it no longer looks sorted end to end.
The job
A sorted list was cut at some unknown point and the front piece moved to the back — so it still LOOKS sorted in two pieces, just not end to end. Find a target value in it.
The obvious way
Ignore the structure entirely and scan every value one at a time.A list of 1,000,000 can cost 1,000,000 checks — binary search's whole advantage looks lost.
The idea
It isn't lost. Split at `mid` as usual — one of the two halves around it is ALWAYS properly sorted (a single rotation can only break sortedness in one spot). Check the target against that sorted half's range in O(1); if it belongs there, search it — otherwise the other half must hold it. Either way, half the array is still safely discarded.
Think of it like this. A shuffled deck that was cut once and the two halves swapped — not shuffled, just cut and rejoined. Fan it open at any point and one of the two sides you're looking at is still in perfect order; you can tell instantly which one, and that's enough to know where to look next.
Searching for 0
7 numbers — sorted, then rotated at some unknown point. Find 0.
def search_rotated(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 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 -1This run
Found 0 at index 4 after 3 looks — still O(log n), even though the array is not fully sorted.
What changed from plain binary search
Which half is sorted
Comparing `nums[lo]` to `nums[mid]` reveals which of the two halves is the properly sorted one — the OTHER half is the one that contains the rotation break.
A range check, not an equality
Once the sorted half is known, checking whether the target falls in ITS min/max range is the same O(1) test ordinary binary search does — just against a half instead of the whole array.
Still exactly one halving per step
Whichever half turns out not to contain the target — sorted or not — is discarded whole. The window still shrinks by half every step, so it is still O(log n).
How to spot this shape
The tell: The data was sorted and then rotated by an unknown amount — so a plain sortedness check fails, but you can still prove one half around any midpoint is properly ordered.
Reach for it when
- The problem explicitly says "rotated sorted array".
- The array looks sorted in two pieces, with one break where it wraps.
- All values are described as unique (duplicates break the "which half is sorted" test — see 81).
- A plain binary search would be the answer if not for the rotation.
Not this when
- The array is rotated an unknown number of times or not sorted at all before rotating — there is no usable structure left.
- Duplicates are present and cause nums[lo] == nums[mid] == nums[hi] — needs a fallback single-step shrink.
- You need every occurrence of the target, not just one.
Practice
6 problemsThe lesson, exactly. Work out which half is properly sorted first, then binary search that half's known range.
Duplicates can make nums[lo] == nums[mid] == nums[hi], which hides which half is sorted — shrink lo and hi by one and retry when that happens.
The rotation point itself, found the same halving way — its own lesson here, worth comparing side by side.
Same rotation-point search, but duplicates force an occasional single-step shrink when nums[mid] == nums[hi].
No rotation here, but the same "which half definitely contains an answer" reasoning drives the halving — its own lesson here too.
Three binary searches chained: find the peak first, then binary search each of the two monotonic halves around it.