Search in Rotated Sorted Array: Binary Search When the Order Is Broken
Solve Search in Rotated Sorted Array in O(log n) — detect which half is still sorted at every mid, keep the half that can hold the target, and halve.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Binary search has one prerequisite: sorted input. Rotate that input — cut [0,1,2,4,5,6,7] at some pivot and glue the front onto the back to get [4,5,6,7,0,1,2] — and the global order is gone. The classic nums[mid] < target comparison no longer tells you which way to go, because "bigger" values now live on both sides of any midpoint.
This problem is the definitive test of whether you understand binary search as an idea rather than a memorized template. The template needs sorted data. The idea only needs one thing: a question you can answer at mid that safely eliminates half the range. Rotated arrays still offer such a question — you just have to find it.
That question turns out to be beautifully simple, and it solves the whole problem in one pass with no preprocessing.
The problem
Given an array of distinct integers nums that was sorted in ascending order and then rotated at some unknown pivot, and a target, return the index of target if it exists, otherwise return -1. The required runtime is O(log n).
Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 0
Output: 4 // nums[4] === 0
Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 3
Output: -1 // 3 is not in the arrayTwo constraints in that statement carry all the weight:
- Distinct values. This is what makes the sorted-half test reliable. With duplicates the guarantee collapses (more on that in the mistakes section).
- O(log n) required. A linear scan is a correct answer and an automatic interview fail. The constraint is the interviewer telling you: binary search survives the rotation somehow — find how.
The brute force baseline
Ignore the structure and scan:
function search(nums, target) {
for (let i = 0; i < nums.length; i++) {
if (nums[i] === target) return i;
}
return -1;
}This is O(n), and it throws away everything the problem hands you. The array isn't random — it's two sorted runs stitched together, and the problem statement explicitly demands logarithmic time. State this baseline in one sentence, then beat it. On 10⁶ elements, O(n) is a million comparisons; O(log n) is about twenty.
The key insight: one half is always sorted
A rotation creates exactly one break point — one place where a larger value is immediately followed by a smaller one. In [4,5,6,7,0,1,2] that break sits between 7 and 0. Everything else is in order.
Now split the array at any mid. The single break point falls into the left half or the right half — never both. Whichever half doesn't contain it is a perfectly ordinary sorted run. So at every step of a binary search:
At least one half is fully sorted, and one comparison tells you which: if nums[left] <= nums[mid], the left half is sorted; otherwise the right half is.
Why does that unlock the problem? Because for a sorted range you can answer "is the target in here?" in O(1) — just check the endpoints. So the loop body becomes: find the sorted half, check whether target falls between its endpoints. If yes, search that half. If no, the target can only be in the other half — search there. Either way, you discard half the range, which is the entire soul of binary search. No pivot-hunting preprocessing needed.
The optimal solution
This is the exact algorithm the visualizer steps through:
var search = function(nums, target) {
let left = 0, right = nums.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (nums[mid] === target) return mid;
if (nums[left] <= nums[mid]) {
// left half [left..mid] is sorted
if (nums[left] <= target && target < nums[mid]) right = mid - 1;
else left = mid + 1;
} else {
// right half [mid..right] is sorted
if (nums[mid] < target && target <= nums[right]) left = mid + 1;
else right = mid - 1;
}
}
return -1;
};Three details deserve attention, because each one is a bug when you get it wrong:
nums[left] <= nums[mid]uses<=, not<. When the window shrinks to two elements,midequalsleft, sonums[left] === nums[mid]. A one-element "half" is trivially sorted, and<=classifies it correctly;<would send you down the wrong branch.- The range checks are half-open on the
midside.target < nums[mid]andnums[mid] < targetare strict because the line above already ruled outnums[mid] === target. Making them inclusive can't return a wrong answer, but strict bounds keep the logic honest:midis done, exclude it. - Both branches move a boundary past
mid(mid - 1ormid + 1). The window shrinks by at least one element every iteration, which is what guarantees termination.
Walkthrough: nums = [4, 5, 6, 7, 0, 1, 2], target = 0
| Step | left | right | mid | nums[mid] | Sorted half | Target in it? | Action |
|---|---|---|---|---|---|---|---|
| 1 | 0 | 6 | 3 | 7 | left: [4,5,6,7] (4 ≤ 7) | 4 ≤ 0 < 7? No | left = 4 |
| 2 | 4 | 6 | 5 | 1 | left: [0,1] (0 ≤ 1) | 0 ≤ 0 < 1? Yes | right = 4 |
| 3 | 4 | 4 | 4 | 0 | — | nums[mid] === target | return 4 |
Step 1 is the signature move: 7 isn't the target, but nums[0] = 4 <= 7 proves the left half is sorted, and 0 can't live between 4 and 7 — so the entire left half dies in one comparison, break point and all.
Step 2 shows the algorithm self-correcting its view of the array. The remaining window [0,1,2] contains no break point, so it behaves like plain binary search from here: the "left half" [0,1] is sorted, the target fits inside it, and the window collapses onto index 4.
Seven elements, three iterations, one answer. Step through it interactively to watch the sorted-half detection fire at each mid.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Linear scan | O(n) | O(1) | ignores the two-sorted-runs structure entirely |
| Find pivot, then two binary searches | O(log n) | O(1) | correct, but two passes and twice the edge cases |
| One-pass modified binary search | O(log n) | O(1) | one comparison classifies the halves; range halves every iteration |
The pivot-first approach (binary search for the rotation point, then ordinary binary search in the correct run) has the same asymptotics, so it isn't wrong — it's just more code, and each extra boundary condition is another place to slip under interview pressure. The one-pass version answers the same questions with a single loop.
Common mistakes
- Using
<instead of<=in the sorted-half test.nums[left] < nums[mid]fails whenleft === mid(a two-element window). The single elementnums[left..mid]is sorted, but strict<claims it isn't, and the search walks into the wrong half. - Inclusive bounds on the
midside of the range checks. Writingtarget <= nums[mid]re-includes an index you already proved isn't the answer. Keeptarget < nums[mid](left branch) andnums[mid] < target(right branch) strict; thenums[mid] === targetcheck above owns that case. - Testing whether the target is in the unsorted half. You can't — its endpoints don't bound its contents (the break point is inside). Always run the membership test against the sorted half and treat the other half as the fallback.
- Assuming it works with duplicates. With
nums = [3,1,3,3,3],nums[left] === nums[mid]no longer proves the left half is sorted. That's the follow-up problem (Search in Rotated Sorted Array II), where the fix — shrinking the window by one when the test is ambiguous — degrades the worst case to O(n). - Special-casing "not rotated." Unnecessary. If the rotation is zero,
nums[left] <= nums[mid]is true at every step, the left-half branch always runs, and the code is plain binary search. The general logic subsumes the special case.
Where this pattern shows up next
This problem sits at the top of a ladder of binary-search-on-a-predicate ideas — each rung replaces "is the array sorted?" with "can I still discard half?":
- Binary Search — the vanilla template this problem deliberately breaks; get the
left <= rightloop and mid math automatic here first. - Guess Number Higher or Lower — binary search where feedback comes from an oracle instead of a comparison you write yourself.
- First Bad Version — boundary-finding binary search: instead of locating one value, locate where a yes/no answer flips.
- Sqrt(x) — binary search over an answer space with no array at all, the fully generalized form of "halve on a monotone condition."
FAQ
Why is one half of a rotated sorted array always sorted?
A single rotation creates exactly one break point — one position where a larger value is immediately followed by a smaller one (like 7 → 0 in [4,5,6,7,0,1,2]). Splitting the array at any midpoint puts that break in the left half or the right half, never both. The half without the break is an unbroken ascending run, so its endpoints fully describe its contents — which is what lets you test "is the target in here?" in O(1).
What is the time complexity of Search in Rotated Sorted Array?
O(log n) time and O(1) space. Each loop iteration does a constant amount of work — one equality check, one sorted-half classification, one range test — and then discards half of the remaining window by moving left past mid or right before it. For an array of a million elements, that's roughly 20 iterations.
Does this solution work if the array contains duplicates?
No. The sorted-half test relies on nums[left] <= nums[mid] proving the left half is ordered, and duplicates break that proof: in [3,1,3,3,3], nums[left] === nums[mid] even though the left half contains the break point. The variant with duplicates (Search in Rotated Sorted Array II) handles the ambiguous case by shrinking the window one element at a time, which drops the worst case from O(log n) to O(n).
Do I need to find the rotation pivot before searching?
No — that's the main appeal of this approach. A pivot-first solution (one binary search to find the rotation point, a second to find the target in the correct sorted run) also achieves O(log n), but it's two loops and twice the boundary conditions. The one-pass version skips pivot-finding entirely: at each step it detects which half is sorted, checks whether the target fits in that half's range, and keeps the only half that can still contain the answer.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.