Why does a wrap-point search in a rotated array shrink with hi = mid, not hi = mid - 1?

## The problem shape A fixed-size capture buffer records monotonically increasing sequence numbers and wraps when full, so a raw dump begins part-way round the ring: an ascending run, one drop, another ascending run. To replay the records in true order you need the index of the drop — the position of the smallest sequence number. That index *is* the rotation offset, so once you have it, the original position of any dumped entry `i` is `(i + offset) mod n`. This is a search with no target. There is no value to compare against, so the usual `found it, return` exit does not exist; instead the range is narrowed until one index survives. ## Why the two branches are asymmetric The loop maintains the invariant **the wrap point lies in `lo..hi`**, and each branch must preserve it. - `a[mid] > a[hi]`: a descent happens somewhere strictly after `mid`, so a value smaller than `a[mid]` exists to the right. The midpoint is therefore disqualified as the minimum, and `lo = mid + 1` both preserves the invariant and shrinks the range. - `a[mid] <= a[hi]`: no descent occurs between `mid` and `hi`, so that whole stretch is ascending and `a[mid]` is the smallest value in it. The minimum of the entire range is thus at `mid` or to its left — `mid` is still a candidate. Writing `hi = mid - 1` would throw away the only correct answer whenever the minimum sits exactly at `mid`, which happens routinely (it happens on the very first iteration of an unrotated array of odd length). Writing `hi = mid` keeps the candidate and still shrinks the range, because `mid < hi` whenever `lo < hi`. ## Why the loop test must be strict Because one branch keeps `mid`, progress is no longer guaranteed for a single-element range. With `while lo <= hi` and `lo == hi`, the midpoint equals both bounds; the comparison `a[mid] > a[hi]` is an equality-driven false, so `hi = mid` reassigns `hi` to the value it already had and the loop repeats identically — a hang, not a wrong answer. The strict test `while lo < hi` exits the moment the range holds one index, and that index is the wrap point. This pairing is the general rule worth internalising: **a branch that keeps the midpoint requires a strict loop condition**; a branch structure that always moves both bounds past the midpoint can use the non-strict one. Mixing a `hi = mid` shrink with a `lo <= hi` test is one of the most common infinite loops in this whole family of searches. ## Why the comparison is against the high endpoint specifically Here, unlike the target-search variant, the anchor choice is not merely stylistic. Comparing the midpoint with the *low* endpoint cannot distinguish two different situations: on an unrotated ascending range, `a[mid] > a[lo]` while the minimum sits at `lo`; on a rotated range with the wrap to the right of `mid`, `a[mid] > a[lo]` as well, and the minimum is to the right. The same observation would demand opposite moves, so the low-endpoint form needs an explicit pre-check (`if a[lo] < a[hi] then return lo`) before it becomes correct. The high-endpoint comparison needs no such guard: on an unrotated range `a[mid] <= a[hi]` always holds, the search keeps moving left, and it lands on index `0` — the right answer. ## Cost On distinct values the range at least halves every iteration, giving O(log n) time and O(1) extra space. For a capture buffer of a few thousand slots that is a dozen comparisons against a few thousand — a real but often irrelevant win, which is a fair thing to say out loud when asked whether you would ship it. ## Testing it honestly The inputs that catch the classic bugs are small and cheap to enumerate: every rotation offset of a four- and five-element array, including offset zero; a single-element range; a two-element range in both rotations. If a solution survives all rotations of a five-element array plus the unrotated case, the boundary logic is almost certainly right; if it only ever gets tried on one hand-picked rotation, an off-by-one can live in it indefinitely.