Rotated Sorted Arrays

## What rotation actually does Take an array that was sorted ascending and rotate it by an unknown offset `k`: the element that used to sit at index `k` now sits at index `0`, and the elements that used to be in front of it wrap around to the end. Values `10 20 30 40 50` rotated by 3 become `40 50 10 20 30`. Nothing was reordered in the circular sense — read the array as a ring and it is still ascending — but read it linearly, which is how indexing works, there is exactly one place where the order breaks: between `50` and `10`. That single break is called the **wrap point** (equivalently, the pivot, or the position of the minimum). A concrete setting: a fixed-size capture buffer records monotonically increasing sequence numbers and overwrites the oldest slot when it fills. Dump its raw storage after a crash and you get exactly this shape — an ascending run, one drop, another ascending run — because the writer was part-way round the ring when it stopped. ## Why the classic discard rule needs more than "mostly sorted" Binary search does not need the array to be *nearly* sorted; it needs a specific implication to hold at every step: > if `target < a[mid]` then the target, if present, lies strictly left of `mid` That implication is licensed only by total order over the index range. In `40 50 10 20 30`, take `mid = 2` with `a[mid] = 10` and search for `40`. Since `40 > 10`, the classic rule discards indices `0..2` and searches `20 30`. The target was at index `0`. The algorithm does not loop forever or crash — it confidently reports *not found*, which is the dangerous failure mode: a silently wrong answer, not an exception. A related wrong instinct is "it is still sorted, just starting somewhere else, so binary search is fine". Circularly sorted is not the same as sorted, and binary search operates on indices, not on the ring. ## The property that does survive Pick any `lo <= mid <= hi`. The wrap point is a single position, so it lies in at most one of the two segments `lo..mid` and `mid..hi`. Therefore **at least one of those two segments is free of the wrap point and is genuinely in ascending order**. (When the offset is `0`, or when the range no longer straddles the wrap, both segments are in order — that is fine, the guarantee is "at least one".) This is what makes the problem tractable in logarithmic time. Each iteration becomes: 1. Determine which segment is in order — by comparing the midpoint value with an endpoint value, never with the target. 2. In that ordered segment, the classic range test applies: the target is inside it if it falls between the segment's two endpoint values. 3. If it does, continue inside the ordered segment; otherwise discard it and continue in the other one, which is where the wrap lives. Either branch halves the range, so with distinct values the cost stays O(log n) — the same bound as ordinary binary search, with a bigger constant because each step does two or three comparisons instead of one. ## Boundaries worth knowing early - **Offset zero is a legal rotation.** Whatever you write must still be correct on an array that was never rotated; several tempting shortcuts fail exactly there. - **The target's value tells you nothing about the offset.** You cannot deduce where the wrap is from the target alone; you deduce it from midpoint-versus-endpoint comparisons. - **Distinct values are doing real work in the O(log n) claim.** Once values repeat, a midpoint can tie with an endpoint and the ordered-side test stops discriminating, which pushes the worst case up to linear. The bound is O(log n) *for distinct values*. - **Sorting first is not a fix.** Sorting costs more than the linear scan you were trying to avoid, and it destroys the recency information the rotation encodes — in the capture-buffer case, the wrap point is precisely what tells you where the oldest record is. ## The honest fallback If you cannot reconstruct the ordered-side reasoning under interview pressure, say so and give the linear scan: it is O(n), obviously correct, and for a buffer of a few thousand entries perfectly adequate. What loses points is claiming the unmodified logarithmic search still works, because that is a correctness error, not a performance one.