Why does a first-true binary search over an answer range set hi = mid instead of mid - 1?

## State the invariant first Every correct binary search is a loop that maintains a window and an invariant. For the first-true search over an answer range the invariant is: > every candidate strictly below `lo` has been shown infeasible, and `hi` is a candidate known to be feasible — so the smallest feasible candidate lies in `lo..hi`. The two branch bodies exist to preserve exactly that sentence, and the return value is justified by it: when the window collapses to a single element, the only place the answer can be is `lo`, which now equals `hi`. ## Why a true probe keeps mid `feasible(mid) == true` is positive evidence: `mid` is a working candidate. Nothing has been learned about anything below it, so the window becomes `lo..mid` — `mid` stays in, because it may be the smallest working candidate. Writing `hi = mid - 1` discards it and, when `mid` was the answer, the loop converges one below it and returns a value that does not work. This is not a cosmetic difference between styles; it is the difference between the search returning the boundary and returning the wrong side of it. `feasible(mid) == false` is the opposite: `mid` is proven not to work, so it can be excluded outright and `lo = mid + 1` preserves the invariant. The asymmetry between the branches — one keeps `mid`, the other drops it — is precisely why the ordinary "search for an exact element" template, which drops `mid` on both sides, cannot be reused unchanged here. ## Why the rounding direction is not free The midpoint must round *away* from the bound that can stall. With `hi = mid`, take a window where `hi == lo + 1`: - Rounding down gives `mid == lo`. If the probe is true, `hi` becomes `lo` and the window collapses; if false, `lo` becomes `lo + 1` and it collapses too. Either way the loop terminates. - Rounding up gives `mid == hi`. A true probe assigns `hi = mid`, which is `hi` — nothing changed, the guard `lo < hi` still holds, and the loop runs forever on identical state. So rounding down pairs with `hi = mid`, and rounding up pairs with `lo = mid`. Choosing one from each pair is the classic hang. Note also that computing the midpoint as `lo + (hi - lo) / 2` rather than `(lo + hi) / 2` avoids overflow when the bounds are large — which matters here more than in array search, because answer ranges are often deliberately enormous. ## Termination With rounding down and `lo < hi`, the midpoint satisfies `lo <= mid < hi`. The true branch sets `hi = mid`, strictly decreasing `hi`; the false branch sets `lo = mid + 1`, strictly increasing `lo`. The window shrinks by at least one on every iteration and roughly halves, so the loop finishes in about `log2(hi - lo + 1)` probes and each probe is one evaluation of the feasibility check. ## What the result means if hi was never proven feasible The invariant assumed `hi` is feasible. If you cannot argue that, the loop still terminates and still returns `lo` — but now `lo` may be a candidate that does not work, because the search only ever finds the flip point *given that a flip exists inside the window*. The fix is one of: prove the upper bound feasible when choosing it, run a single check on the returned value before using it, or handle "no feasible candidate in range" as an explicit outcome. Silently trusting a returned bound is where the technique produces plausible, wrong numbers. ## The mirror image For the largest feasible candidate the invariant flips: everything above `hi` is known infeasible, `lo` is known feasible, midpoint rounds up, a true probe sets `lo = mid`, a false probe sets `hi = mid - 1`, and the answer is `lo` at collapse. It is the same proof read backwards. Teams that keep one written form of each and reuse them see far fewer boundary bugs than teams that re-derive the loop each time. ## Continuous ranges When the candidate is a real number there is no `mid + 1` and no collapse to a single element: `lo < hi` is essentially always true, so the loop needs a different stopping rule. A fixed number of halvings — around a hundred — shrinks any realistic starting interval far below the resolution the numbers can even represent, and it terminates in a predictable, bounded time. A condition like "stop when the gap falls below a small epsilon" can never be satisfied when the gap is already at the spacing between representable values near those magnitudes, and the loop simply never ends. ## The bugs this section is really about Returning `mid` as soon as a probe is true (it is *a* feasible value, not the smallest); using the exact-match template that drops `mid` on both branches; pairing round-up with `hi = mid`; and returning `lo` from a range where nothing was feasible. All four survive tests that only probe the middle of the range, which is why boundary cases — the answer at `lo`, the answer at `hi`, no answer at all — are the tests worth writing.