Lower Bound, Upper Bound, and the Invariant That Makes Binary Search Correct

The usual formulation of binary search — “compare with the middle element, then go left or right” — is a description of a search tree traversal, not an algorithm. It leaves the hard parts unspecified: which element counts as the middle when the range has even length, what happens when the key is absent, and what to return when duplicates are present. Every one of those gaps has produced a documented defect in a standard library. The formulation that closes them is a loop invariant over a half-open index interval.

Two questions hide behind “find the key”

A sorted array supports at least four distinct queries, and conflating them is the source of most binary search bugs.

• Exact membership. Does the value appear at all?
• Lower bound. What is the first index whose element is not less than the query?
• Upper bound. What is the first index whose element is greater than the query?
• Insertion point. Where must a value go so the array stays sorted? For a value already present, the answer depends on whether the caller wants it before or after the existing equal run.

Lower bound and insertion point coincide when the array holds distinct keys. With duplicates they diverge, and the divergence is exactly what makes lower_bound and upper_bound two functions rather than one function with a flag. The pair also brackets the equal range: for a sorted array a, every index in [lower_bound(x), upper_bound(x)) holds a value equal to x, and the count of occurrences is the difference of the two bounds. That identity is the reason a range query over duplicates can be answered with two searches instead of a scan.

The invariant is the whole algorithm

The formulation that works maintains a half-open interval [lo, hi) and the claim that everything before lo is strictly less than the query, while everything at or after hi is greater than or equal to it. The interval shrinks by moving one endpoint to the midpoint. When lo == hi the interval is empty and lo is the answer: the first position not holding a smaller value.

/* Returns the first index i with a[i] >= key, or n if none exists.
   Requires a[0..n) sorted ascending. */
size_t lower_bound(const int *a, size_t n, int key)
{
    size_t lo = 0, hi = n;          /* invariant: a[0..lo) < key <= a[hi..n) */
    while (lo < hi) {
        size_t mid = lo + (hi - lo) / 2;   /* never overflows */
        if (a[mid] < key)
            lo = mid + 1;           /* a[mid] is too small: discard it */
        else
            hi = mid;               /* a[mid] may be the answer: keep it */
    }
    return lo;
}

Three properties of this code carry the correctness argument. The interval is half-open, so hi is a legal position one past the last element and n is a valid return value for “not found”. The update hi = mid rather than mid - 1 is what keeps a candidate alive; using mid - 1 is correct only when the comparison is for equality and the element is known to differ. And the loop terminates because mid is strictly less than hi whenever lo < hi, so each iteration strictly shrinks the interval. The termination argument fails if the midpoint can equal hi, which happens if the interval is written as [lo, hi] with hi = n - 1 and the arithmetic rounds up.

Writing the comparison as a predicate rather than a three-way branch generalises the routine. Any monotone predicate — “is this timestamp at or after the cutoff”, “is this element greater than the query” — partitions the array into a false prefix and a true suffix, and the same loop finds the boundary in ⌈log₂(n+1)⌉ predicate evaluations. That is how a search over a sorted array becomes a search over an arbitrary monotone property, including properties that cannot be evaluated by comparing two stored values.

Arithmetic that breaks before the algorithm does

The midpoint expression (lo + hi) / 2 is the most-copied line in the literature and it overflows. With 32-bit signed indices, lo + hi exceeds 2³¹ − 1 once the array length passes 2³⁰, and the sum wraps to a negative number, which then indexes outside the array. The defect was present in java.util.Arrays.binarySearch for years and is the reason the recommended form is lo + (hi - lo) / 2, or the unsigned shift (lo + hi) >>> 1 where indices are non-negative. Neither expression is slower: compilers turn both into a shift or a divide of a difference that already exists.

Two other arithmetic hazards are less famous.

• Element arithmetic, not index arithmetic. Interpolation search computes a probe position from the values themselves, and (key - a[lo]) * (hi - lo) overflows a 64-bit integer when the key range approaches 2⁶³. The search is correct in exact arithmetic and wrong in machine arithmetic.
• Sentinel keys. A common optimisation appends a copy of the query at the end of the array so the inner loop can drop the bounds check. It works for exact membership, but it silently changes the meaning of a lower-bound search, because the sentinel is now an element that satisfies the predicate.

What the branch costs, and why layout matters

A binary search over n elements performs at most ⌈log₂(n+1)⌉ comparisons, so a billion elements need 30 probes and a million elements need 20. Each probe touches a different region of memory: the first at the midpoint, then a quarter point, and so on. The first several probes miss cache; later ones hit. The total is dominated by memory latency rather than comparison count, with a DRAM access costing on the order of a hundred nanoseconds and an L1 hit a few cycles.

The branch is the second cost. Whether the next probe goes left or right is data-dependent and, for random keys, unpredictable; a mispredicted branch costs roughly fifteen to twenty cycles on current x86 cores, which can exceed the cost of the comparison by an order of magnitude. Two responses exist. The first is to make the traversal branch-free with conditional moves, so the next index is selected arithmetically; the second is to change the layout so consecutive probes fall in the same cache line, which is the idea behind the Eytzinger layout. Both trade a small amount of extra work per step for a large reduction in stalls.

The comparison count is also not the same as the probe count when the array stores variable-length records. A sorted array of offsets into a heap is a common compromise: the search touches only 4- or 8-byte keys, and the record is fetched once at the end. This keeps the probe count unchanged and reduces the bytes moved per probe by whatever the record size exceeds the key size.

Duplicates, and the family of off-by-one errors

With duplicates the exact-membership variant has no defined answer, because any index in the equal run is correct. Callers that treat the returned index as the start of the run are then wrong in a way that depends on the input. A three-way comparison loop that returns as soon as it sees equality is fast and useless for range queries; the bound formulation is slower by at most one iteration and answers the stronger question.

The classic failure modes, all reproducible:

Symptom	Cause
Loop never ends	Interval written as [lo, hi] with mid rounding down and lo = mid
Answer off by one for absent keys	Returning mid instead of lo on exit
Crash on empty input	Initialising hi = n - 1 for n = 0, giving an unsigned underflow
Wrong answer for the last element	hi = mid - 1 with mid equal to the candidate
Duplicate run truncated	Returning an arbitrary equal index rather than a bound

The empty-array case deserves the emphasis it rarely gets. In C, size_t underflow turns n - 1 into SIZE_MAX, and the midpoint computation then produces a huge index that passes any mid < n check written with the same unsigned type. In languages with exceptions the failure is a bounds error; in C it is a read of unmapped memory. The half-open formulation has no special case for n = 0: lo = hi = 0 and the loop does not execute.

When the sorted array stops being the right structure

Binary search requires random access with O(1) index arithmetic. On a rotating disk or a network store, each probe is a seek, and 20 probes mean 20 seeks; the structure that fixes this is not a better search but a different index, which is why on-disk exact-match lookup is often built on extendible hashing instead of a sorted file. For a linked list, binary search is impossible without an index; skip lists and balanced trees exist precisely to provide logarithmic search over linked nodes.

There is also a lower bound that no implementation beats. Comparison-based search among n ordered keys requires at least ⌈log₂(n+1)⌉ comparisons in the worst case, by the decision-tree argument: each comparison has two outcomes, so a tree with n + 1 possible answers needs that many leaves. Every optimisation discussed above reduces constants and memory traffic; none reduces the count of comparisons below the information-theoretic floor. Breaking that floor requires assumptions beyond ordering — a uniform key distribution, as interpolation search exploits, or a computable hash function, which is what turns lookup into an array index.