Run it
The search with each decision printed, checked against a linear scan at every rotation of the same array, plus the duplicates variant and its O(n) case.
The key property
Split at the midpoint. The rotation point lies in one half or the other, so the other half is properly sorted. Comparing nums[mid] with nums[left] reveals which:
nums[left] <= nums[mid] → the left half is sorted. Otherwise → the right half is sorted.
Once the sorted half is identified, checking whether the target lies within its range is a simple bounds test. If it does, search there; if not, search the other half.
O(log n) time, O(1) space.
The <= in nums[left] <= nums[mid] is not cosmetic. When the subarray has two elements, left == mid, and a strict < would misclassify the halves and send the search the wrong way. Cases like [3, 1] searching for 1 are where this shows up.
The inclusive-exclusive asymmetry in the bounds tests is deliberate too: nums[left] <= target < nums[mid] excludes mid because that value has already been compared and rejected. Making both ends inclusive re-tests a known-failed position, and while it does not break correctness, it does obscure the reasoning.
Why binary search survives rotation
A rotation splits the array into two sorted runs. Wherever mid lands, it is inside one of them — so at least one of [lo, mid] and [mid, hi] is entirely in order. That is the invariant the whole solution rests on, and it holds for any rotation amount including zero.
values[lo] <= values[mid] identifies which. Use <=, not <: when lo == mid the left half is a single element and is trivially sorted.
The decision that follows
Having found a sorted half, you can test membership by range rather than by searching. If the target lies between that half's endpoints, it can only be there. If it does not, it can only be in the other half. Either way one half is discarded per step.
The bounds matter: values[lo] <= target < values[mid] on the left, and values[mid] < target <= values[hi] on the right. mid has already been compared, so it is excluded on both sides.
The duplicates variant
With duplicates allowed, values[lo] == values[mid] == values[hi] tells you nothing about which half is sorted, and the only safe move is to shrink the window by one. That makes the worst case O(n) — and it is a genuine lower bound, not a lazy implementation.
Saying "O(log n), but O(n) worst case if duplicates are allowed" is the complete answer, and the follow-up interviewers reach for when the first part goes smoothly.
Tracing it
[4, 5, 6, 7, 0, 1, 2], target 0:
| left | right | mid | nums[mid] | Sorted half | In range? | Action |
|---|
| 0 | 6 | 3 | 7 | Left (4 ≤ 7) | 0 not in [4, 7) | Go right |
| 4 | 6 | 5 | 1 | Left (0 ≤ 1) | 0 in [0, 1) | Go left |
| 4 | 4 | 4 | 0 | — | — | Found at 4 |
Three iterations for seven elements — log₂ 7 ≈ 2.8, as expected.
The duplicates problem
With duplicates allowed, the guarantee breaks. Consider [1, 1, 1, 0, 1, 1, 1]: here nums[left] == nums[mid] == nums[right] == 1, and there is no way to tell which half contains the rotation. The comparison carries no information.
The standard mitigation is to skip the ambiguous boundary:
Average O(log n), worst case O(n) — and the worst case is unavoidable. An array of all equal values with one different element cannot be searched faster than linearly, because no comparison narrows the range. Saying that outright is a better answer than claiming O(log n).
Note that this variant is usually posed as "does the target exist" rather than "at what index", because with duplicates the index is not unique.
The two-pass alternative
Some find this easier to reason about: first find the rotation point, then do an ordinary binary search on the correct segment.
Two O(log n) passes, so still O(log n). The pivot search is itself a well-known problem ("find minimum in rotated sorted array"), and it uses nums[right] for comparison rather than nums[left] — comparing against nums[left] fails on an unrotated array.
| Approach | Time | Space | Notes |
|---|
| Linear scan | O(n) | O(1) | Ignores the constraint |
| Modified binary search | O(log n) | O(1) | One pass, the expected answer |
| Find pivot, then binary search | O(log n) | O(1) | Easier to reason about |
| With duplicates | O(n) worst | O(1) | Unavoidable |
Find the minimum in a rotated sorted array. The pivot search above, on its own.
How many times was it rotated? The index of the minimum.
Find a peak element. Binary search on a different local property — move towards the larger neighbour.
Search a 2D matrix where rows and columns are sorted. Start from a corner and eliminate a row or column per step.
Binary search on the answer. The broader technique — "minimum capacity to ship packages in D days", "split array largest sum" — binary searching a value range rather than an array.
The common thread: binary search needs a monotonic predicate, not a sorted array. Once that is the framing, rotated arrays, peaks and answer-space searches all become the same tool.
What it is testing
Do you spot that one half is always sorted? This is the insight the problem exists to test.
Do you get the <= right? With left == mid in a two-element subarray, a strict comparison misroutes the search.
Do you handle no rotation? A fully sorted array is a valid input and must still work.
Do you ask about duplicates? A good question to raise unprompted, and the honest answer is that they force O(n) in the worst case.
Are your bounds consistent? while left <= right with mid ± 1 updates, or an off-by-one causes an infinite loop.
Recap in one screen
- At least one half of any subarray is sorted;
nums[left] <= nums[mid] identifies which. - Test whether the target lies inside the sorted half's range, and search that half if so.
- The
<= matters because left == mid when only two elements remain. - Duplicates destroy the guarantee and force O(n) worst case — skip equal boundaries and say so.
- Binary search needs a monotonic predicate, not literally a sorted array.