Search in Rotated Sorted Array
A sorted array was rotated at an unknown pivot. Find target's index in O(log n), or −1.
- 1 <= nums.length <= 5000
- -10⁴ <= nums[i] <= 10⁴
- All values of nums are unique.
- nums is an ascending array that is possibly rotated.
- -10⁴ <= target <= 10⁴
Intuition
Search in rotated sorted array takes a sorted array that has been rotated at some unknown pivot — [4,5,6,7,0,1,2] — and asks for a target's index in O(log n). The array is no longer sorted, so plain binary search fails: comparing the target against the middle element no longer tells you which side to keep.
The property that rescues it is easy to miss and easy to prove. Cut the array anywhere, and at least one of the two halves is still perfectly sorted. The rotation introduces exactly one "drop" point, and that point can only fall on one side of the midpoint — so the other side is untouched, ordered, and behaves normally.
That gives a two-step decision at each iteration:
- Work out which half is sorted by comparing nums[lo] with nums[mid].
- Test whether the target lies inside that half's known range. If it does, search there. If not, the target must be in the messy half.
The second step is the key move. You never need to understand the unsorted half — you only need to rule the sorted half in or out, and a sorted half has a known minimum and maximum, so that test is a single range check.
Each iteration still discards half the array, so the O(log n) bound survives the rotation intact.
Binary search doesn't actually require a sorted array — it requires that you can discard half at each step. Here the array is broken into two sorted runs, and the key observation is that at least one side of mid is always sorted. Identify which one, test whether the target lies inside its known range, and you've recovered the discard rule. Any problem where you can name a predicate that flips exactly once is binary-searchable.
Approach
Before reading on: price up what sorting first costs here, then ask what property lets you throw away half the range after one comparison. Aim for O(log n) time and O(1) space.
Rely on one half always being sorted
The rotation creates a single drop point, which can lie on only one side of mid. The other side is therefore fully sorted, and that guarantee is what makes a modified binary search possible at all.
Identify the sorted half
If nums[lo] <= nums[mid], the left half is sorted; otherwise the right half is. Use <= rather than < so a two-element window where lo == mid is classified correctly rather than falling through.
Range-test the target against the sorted half
A sorted half has a known first and last value. If the target lies between them, discard the other half; if not, the target can only be in the messy half, so discard the sorted one. You never have to reason about the unsorted side directly.
Use inclusive comparisons in the range test
The test is nums[lo] <= target < nums[mid] for a sorted left half, and nums[mid] < target <= nums[hi] for a sorted right half. Getting one boundary wrong makes the search skip past the target and report −1 on a value that is present.
Return −1 when the window closes
If lo passes hi without a hit, the target is absent. Every step was forced by a comparison against a fully known range, so no backtracking is needed to be sure.
Cost of the modified search
Each iteration still halves the search space, giving O(log n) time and O(1) space. The rotation costs nothing asymptotically — only a slightly more careful discard rule.
Solution & live demo
Common pitfalls
Comparing nums[mid] with nums[hi] to detect rotation
if nums[mid] <= nums[hi]: # right half sorted
...if nums[lo] <= nums[mid]: # left half sorted
...Both framings can work, but they need matching range tests, and mixing one convention's branch with the other's bounds is the usual source of silent wrong answers. Pick the lo-anchored form and keep the comparisons consistent with it.
Using < in the sorted-half test
if nums[lo] < nums[mid]:
if nums[lo] <= nums[mid]:
When the window narrows to two elements, lo == mid, so a strict comparison declares the left half unsorted and sends the search down the wrong branch. Equality means a single-element left side — which is trivially sorted.
Testing the target range with the wrong strictness
if nums[lo] <= target <= nums[mid]: hi = mid - 1
if nums[lo] <= target < nums[mid]: hi = mid - 1
nums[mid] == target was already handled and returned above, so including mid in the range accomplishes nothing and muddies the invariant. The half you keep must exclude the position you've already ruled out.
Edge cases
Left half is always sorted → degenerates to plain binary search.
mid=0, left half [3] sorted; range tests still route correctly.