Why does a half-open lower bound search assign hi = mid rather than hi = mid - 1?

## The invariant is the whole algorithm Every correct binary search is a loop invariant with some arithmetic attached. For the half-open boundary template the invariant is: > The first index satisfying the predicate lies in `[lo, hi]`. Concretely: every index `i < lo` has `a[i] < target`, and every index `i >= hi` has `a[i] >= target` (vacuously true when `hi == n`). Everything else follows mechanically. The two branches are not symmetric, and their asymmetry is the answer to the question. ## Why the passing branch keeps mid When `a[mid] >= target`, mid *satisfies the predicate*. But the algorithm is not looking for **a** satisfying index — it is looking for the **first** one. So mid is a candidate that may or may not be beaten by something to its left. Discarding it with `hi = mid - 1` destroys the invariant: after that assignment, index `mid` is neither below `lo` (so it is not known to fail) nor at-or-above `hi` (so it is not retained as known-good) — it has simply fallen out of the accounting, and if nothing to its left qualifies, the loop has no way to get back to it. A two-element counterexample settles it. Take `a = [3, 5]`, target `5`. Correct version: - `lo=0, hi=2` → `mid=1`, `a[1]=5 >= 5` → `hi=1`. - `lo=0, hi=1` → `mid=0`, `a[0]=3 < 5` → `lo=1`. - `lo == hi == 1` → return **1**. Correct: index 1 holds the first element at least 5. Broken version with `hi = mid - 1`: - `lo=0, hi=2` → `mid=1`, `a[1]=5 >= 5` → `hi=0`. - `lo == hi == 0`, loop exits → return **0**. Wrong: `a[0]` is 3, which is below the target. The bug does not crash, does not loop forever, and returns a plausible in-range index. That is what makes it dangerous — it is a wrong-answer bug, not a fault. ## Why the failing branch does use mid + 1 When `a[mid] < target`, mid is *definitively* not the answer, because it fails the predicate outright. Excluding it is not merely allowed, it is required for termination: if the failing branch wrote `lo = mid` instead, then with `hi == lo + 1` the midpoint rounds down to `lo`, the assignment changes nothing, and the loop spins forever. So the two branches have genuinely different obligations — one must retain its midpoint to stay correct, the other must exclude its midpoint to make progress. Candidates who try to "tidy" the loop into symmetry break one or the other. ## Why `while lo < hi` and not `<=` With a half-open range, `lo == hi` means *empty*: there is nothing left to examine, and by the invariant everything at or above `hi` qualifies while everything below `lo` does not, so `lo` is precisely the first qualifying index. Using `<=` would examine an index outside the intended range and, in the `hi == n` case, read past the end. Termination is easy to argue: `mid` always satisfies `lo <= mid < hi` when `lo < hi`, so `hi = mid` strictly decreases `hi` and `lo = mid + 1` strictly increases `lo`. The range shrinks by at least one every iteration, and roughly halves, giving O(log n) iterations. ## Why the midpoint is computed that way `mid = lo + (hi - lo) / 2` and `mid = (lo + hi) / 2` are mathematically identical and differ in fixed-width integer arithmetic: the second can overflow when both endpoints are large, producing a negative or wrapped midpoint and a wild memory access. The first form only ever adds a non-negative half-width to `lo`. This is a famous, long-undetected class of bug in published binary searches, and mainstream runtimes vary in whether the overflow silently wraps, traps, or is impossible because integers are arbitrary-precision — which is exactly why the safer form is worth writing unconditionally rather than reasoning about your host's arithmetic. ## The template generalises Nothing in the loop depends on the predicate being `a[i] >= target`. Swap in `a[i] > target` and the same code returns the upper bound. Any *monotone* predicate — false on a prefix, true on the remaining suffix — works unchanged, which is why this one loop is worth memorising as a shape rather than as a special case. What must be true is the monotonicity: if the predicate flips back and forth, halving discards the wrong side and the returned index is meaningless. ## Returning `lo` when nothing qualifies If the predicate is false everywhere, `lo` climbs all the way to `n` and the loop exits with `lo == hi == n`. Returning it is correct, not a fallthrough bug: `n` is the legal insertion position past the end. No separate "not found" branch is needed, and adding one is a sign the invariant was never understood.