How do you decide which half of a rotated sorted array is in order at each step?
answer
- two questions per step, not one
- the target answers only the second one
- compare the midpoint against a range endpoint
- midpoint not above the high end means no break there
- then test the target between that side's endpoints
basics
~20 sCompare the midpoint value against a range endpoint, never against the target. If the midpoint value is at most the value at the high end, the segment from midpoint to high is in order; otherwise the low-to-midpoint segment is.
solid answer
~50 sThe decision is made against an **endpoint**, not against the target. Testing `a[mid] <= a[hi]` asks whether the range from `mid` to `hi` contains a wrap point: if the value at the midpoint has not risen above the value at the high end, no break lies between them, so that segment is ascending; if it has, the break must be in there, which means the other segment `lo..mid` is the ordered one. Only after you know which side is ordered do you bring in the target, and then only as a range test against that side's two endpoint values — is the target strictly between them? If yes, continue there; if no, continue in the other side. Comparing the target to `a[mid]` first is the classic error: in a rotated range that comparison implies nothing about which side to keep.
code
pseudocode · 13 lines// a: distinct keys, ascending, then rotated by an unknown offset
while lo <= hi
mid = lo + (hi - lo) / 2
if a[mid] == target
return mid
if a[mid] <= a[hi] // segment mid..hi holds no wrap
if a[mid] < target and target <= a[hi]
lo = mid + 1
else
hi = mid - 1
else // segment lo..mid holds no wrap
...
return NOT_FOUNDgo deeper
Recall the order of operations: first find which side is in order by comparing the midpoint to an endpoint, then check the target against that side's endpoints. Saying 'compare the target to the midpoint' is the answer to avoid.
Explain why the endpoint comparison is decisive — a single wrap point can sit in only one segment — and walk a small rotated example through two iterations, naming which side each test keeps.
Demonstrate boundary discipline: which comparisons are strict, what happens when the window shrinks to one or two entries, and how you would test it — every rotation offset over a small array, plus offset zero.
Weigh whether this invariant belongs in your codebase at all. It is compact but easy to break in review; if the wrap position can be recorded at write time, the whole branch structure disappears.
## Two comparisons, in the right order Each iteration of a rotated-range search answers two separate questions, and mixing them up is where most incorrect solutions come from: 1. **Structural question:** which of `lo..mid` and `mid..hi` is free of the wrap point? Answered by comparing `a[mid]` with an *endpoint value*. 2. **Membership question:** does the target fall inside that ordered segment? Answered by comparing the target with that segment's *two endpoint values*. The target plays no part in question 1. That is the single most important thing to say out loud, because the instinctive move — carried over from ordinary binary search — is to compare the target with `a[mid]` and pick a side. In a rotated range, `target > a[mid]` is compatible with the target being on either side, so that comparison alone decides nothing. ## Why the high endpoint is the conventional anchor With distinct values, `a[mid] <= a[hi]` holds exactly when the segment `mid..hi` contains no wrap point. The reasoning: within a rotated array, values ascend continuously except across the single break, so if the value at `mid` has not exceeded the value at `hi`, no descent occurred between them. The test degenerates gracefully. When the range shrinks until `mid == hi`, the comparison is an equality, the test reports the one-element segment `mid..hi` as ordered — which is true — and the subsequent range test `a[mid] < target and target <= a[hi]` is unsatisfiable for a value not equal to `a[mid]`, so the search correctly moves left. No special case is needed. The low-endpoint form, `a[lo] <= a[mid]` meaning `lo..mid` is ordered, is equally valid *as long as the comparison is non-strict*. Written strictly as `a[lo] < a[mid]`, it misclassifies the moment the window shrinks to `lo == mid`: the values are equal, the test says "left not ordered", and the algorithm takes the branch built for the opposite structure. That is why the high-endpoint form is the safer default — its natural writing is already correct — but the honest statement is that both anchors work when written carefully, and neither works when compared against the target. ## The membership test, spelled out Suppose the ordered segment is `mid..hi`. The target lies in it precisely when `a[mid] < target and target <= a[hi]`. The asymmetric brackets matter: `a[mid]` was already tested for equality with the target at the top of the loop, so it is excluded, while `a[hi]` has not been tested and must be included. Get that backwards and you drop targets that sit exactly on an endpoint — a bug that only shows up on a small fraction of inputs and survives casual testing. Symmetrically, when the ordered segment is `lo..mid`, the target lies in it when `a[lo] <= target and target < a[mid]`. ## A worked scenario An on-call roster for a week was stored in shift order and then rotated by an unknown offset so the dump begins mid-week; each record carries an ordering key. Searching for one person's slot: at each step you ask which side of the current window is still in shift order, then whether that person's key falls between that side's first and last keys. Notice the records are compared only through their keys — the technique does not care whether the payload is a sequence number or a roster entry, only that the keys are comparable and were ascending before rotation. ## Cost and correctness Each iteration performs a constant number of comparisons and halves the range, so the search is O(log n) time and O(1) extra space in the iterative form, on distinct keys. Written recursively it is O(log n) stack depth, which counts toward space. ## What to say when asked to justify it The proof obligation is small and worth stating: the wrap point occupies one position; splitting at `mid` puts it in at most one segment; the endpoint comparison identifies which; the range test on the ordered segment is exact because that segment really is sorted; therefore each step preserves the invariant "if the target is present, it is in `lo..hi`" while halving the range. Termination and correctness follow from that invariant, not from the shape of the code.
- Can you anchor on the low endpoint instead of the high one?Yes, if you write it non-strictly: `a[lo] <= a[mid]` means the segment `lo..mid` is ordered. The strict form `a[lo] < a[mid]` breaks once the window shrinks to `lo == mid`, where the values are equal and the test wrongly reports the left side as unordered. The high-endpoint form is preferred because its natural writing is already safe.
- Why is the range test on the ordered side written with asymmetric bounds?The midpoint value has already been compared with the target for equality at the top of the loop, so it is excluded from the range; the far endpoint has not been tested and must be included. Getting the inclusivity backwards silently loses targets that sit exactly on an endpoint of the ordered segment.
- What if the range is already fully in order?The endpoint test simply reports the whole range as ordered and the search behaves exactly like an ordinary binary search for the rest of its run. No special case is required, which is a good sanity check: a correct implementation must handle an offset of zero as an ordinary input.
saying these in an interview costs you the question
- Compares the target with the midpoint to pick a side
- Assumes the ordered half is always the same side
- Uses a strict comparison against the low endpoint and breaks on tiny windows
- Tries to locate the wrap point first, then searches, without noticing both are logarithmic
- Gets the endpoint inclusivity wrong and loses targets sitting on a boundary