← Browse / Searching

Algorithm B: Binary Search (Lower Bound)

TAOCP Vol. 3, §6.2.1

Knuth §6.2.1 Searching

Given a sorted array $a$ of size $n$ and a value $target$, find the leftmost insertion point: the smallest index $lo$ such that every element at index $\geq lo$ is $\geq target$. Equivalently:

If $target$ is present in $a$, return the index of its first occurrence.
If $target$ is absent, return the index at which it would be inserted to keep $a$ sorted.

This is the shape of C++'s std::lower_bound and Python's bisect.bisect_left.

Why lower bound, not exact match. Knuth's Algorithm B in TAOCP §6.2.1 is the textbook exact-match form: return the index of some occurrence of $target$, or report "not found." Pedagogically clean. But it falls apart on the moment interviewers care about most: duplicates. Given $a = [1, 2, 2, 2, 3]$ and $target = 2$, exact-match binary search might land on index 1, 2, or 3 depending on how ties are broken. Lower bound always returns the leftmost — index 1 — which is what you need when the problem says "the first occurrence," "the number of values strictly less than $target$," or "where would I insert $target$."

The same lower-bound shape generalizes far beyond array search. Any monotone predicate $f$ admits a binary search: "find the smallest $k$ such that $f(k)$ is true." Specialize $f(i) = (a[i] \geq target)$ and you have lower bound on an array; specialize $f(c) = (\text{can finish in capacity } c)$ and you have the capacity binary search family (Koko eating bananas, ship-within-D-days, splitting an array into K subarrays). The half-open window and the asymmetric narrowing — lo = mid + 1 vs hi = mid — are the same in every variant.

The half-open window. Notice that $lo$ is inclusive but $hi$ is exclusive: we search $a[lo..hi)$, not $a[lo..hi]$. This is what makes the narrowing rules in B4 symmetric. Writing hi = mid (rather than hi = mid - 1) keeps $mid$ as a candidate when $a[mid] = target$, while still strictly shrinking the window because $mid < hi$.

Overflow-safe midpoint. Computing mid = (lo + hi) / 2 is the textbook formula, but lo + hi can overflow a fixed-width integer when both indices grow large. The equivalent mid = lo + (hi - lo) / 2 avoids this. This is the bug that lived in java.util.Arrays.binarySearch for nine years — worth internalizing.

The trace below shows $lo$, $hi$, and $mid$ at every labeled state on the example $a = [1, 3, 5, 7, 9, 11, 13, 15]$, $target = 7$. Step through it: each iteration strictly contracts the window, and at termination $lo = hi$ marks the answer.

Computation Method

Initialize

Set $lo \leftarrow 0$ and $hi \leftarrow n$, where $n$ is the array length. The half-open window $a[lo..hi)$ starts as the entire array.

$lo \leftarrow 0,\ hi \leftarrow n$

Test for completion

If $lo \geq hi$, the search window is empty — go to step B5. Otherwise continue to step B3.

$lo \geq hi \rightarrow$ goto B5

Compute midpoint

Set $mid \leftarrow lo + \lfloor (hi - lo) / 2 \rfloor$. The equivalent form $\lfloor (lo + hi) / 2 \rfloor$ is mathematically identical but can overflow when $lo + hi$ exceeds the integer range; the subtractive form is overflow-safe.

$mid \leftarrow lo + \lfloor (hi - lo) / 2 \rfloor$

Compare and narrow

If $a[mid] < target$, every index $\leq mid$ is ruled out, so set $lo \leftarrow mid + 1$. Otherwise $a[mid] \geq target$, so the target (if present) lies at $mid$ or earlier, and we set $hi \leftarrow mid$ — keeping $mid$ as a candidate. Return to step B2.

$a[mid] < target \rightarrow lo \leftarrow mid + 1$; else $hi \leftarrow mid \rightarrow$ goto B2

Output insertion point

Return $lo$ — the leftmost index at which $target$ could be inserted to keep $a$ sorted. To test for membership: $target$ is present if and only if $lo < n$ and $a[lo] = target$.

return $lo$

Why It Works

Key Identity

$$\text{Loop invariant: if } target \in a, \text{ then } target \in a[lo..hi)$$

The invariant holds at B1: the window is the whole array. Each B4 narrowing preserves it. If $a[mid] < target$, sortedness rules out every index $\leq mid$, so $lo \leftarrow mid + 1$ is safe. If $a[mid] \geq target$, the target (if present) must lie at $mid$ or earlier, so $hi \leftarrow mid$ is safe — note that $mid$ stays *inside* the new window because $hi$ is exclusive. The window strictly shrinks each iteration (since $lo \leq mid < hi$ at B3), so the loop terminates in at most $\lceil \log_2 n \rceil + 1$ iterations. At termination, $lo = hi$ marks the partition point: every index $< lo$ has value $< target$ and every index $\geq lo$ has value $\geq target$. That is precisely the leftmost insertion point.

Interactive Trace

Step through a lower-bound binary search on a sorted array. The live window a[lo..hi) is tinted; mid is outlined at each comparison; the window strictly shrinks each iteration.

Complexity: $\Theta(\log n)$ / Space: $\Theta(1)$ — Each iteration halves the window, so the number of B3 / B4 cycles is $\Theta(\log n)$. Space is constant — three indices and no auxiliary storage. The $\Omega(\log n)$ lower bound is tight under the comparison model (a standard decision-tree argument). Knuth's Algorithm B in TAOCP §6.2.1 is the exact-match form; we ship the lower-bound variant here because it composes correctly with duplicates (always returns the leftmost occurrence) and generalizes to the family of *binary-search-on-a-predicate* problems that recur throughout interview prep.

Review Cards

Conceptual Step

What does step B5 do in Binary Search (Lower Bound), and why does it guarantee progress toward termination?

Invariant

What mathematical identity ensures correctness at each step of Algorithm B?

When to Use

When would you reach for Binary Search (Lower Bound) over alternative approaches?

Complexity

What is the time complexity of Binary Search (Lower Bound)?