Binary Search

Binary search repeatedly discards half of an ordered search interval. Its most reusable form finds a boundary rather than stopping at an arbitrary equal value.

Try target 2 first: finding a matching value does not finish a lower-bound search. Then try 5 to see why the answer can be a position beyond the last element.

Watch the search interval shrink

Advance one comparison at a time. The value row stays fixed; only the search boundaries move.

Target value0235

01lo

12 

22mid

34 

4∅hi

Top: index. Blue underline: unknown interval. Dashed outline: midpoint. Green outline: answer. ∅ marks position 4, beyond the array.

Step 0 · [lo, hi) = [0, 4)2 < 2 → hi = 2The next step applies this comparison. Equality moves hi left, so an earlier duplicate is still considered.

Lower bound

This implementation returns the first position whose value is at least the target, using the half-open interval $[lo, hi)$:

def lower_bound(values: list[int], target: int) -> int:
    lo, hi = 0, len(values)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if values[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo

Trace, sentinel, and predicate direction

For values = [1, 2, 2, 4] and target 2:

Before (lo, hi)	mid	Comparison	After (lo, hi)
(0, 4)	2	2 < 2 is false	(0, 2)
(0, 2)	1	2 < 2 is false	(0, 1)
(0, 1)	0	1 < 2 is true	(1, 1)

The first comparison finds a 2 at index 2, but an earlier 2 may exist. hi = mid removes index 2 from the unknown interval while retaining it as a possible answer at the right boundary. The next comparison does the same at index 1. Only index 0 is proved too small, so lo = mid + 1 skips it. The bounds meet at 1, the first duplicate.

The return value can be len(values), an insertion sentinel, not an index to dereference. Empty input returns 0, a target below all keys returns 0, and one above all keys returns n. This matches the partition contract of Python bisect_left.

Exact membership then becomes:

position = lower_bound(values, target)
found = position < len(values) and values[position] == target

Invariant

All positions before lo are known to be too small; all positions at or after hi are known to satisfy the boundary condition. The unknown region is [lo, hi). Each iteration shrinks it, and termination at lo == hi identifies the boundary.

Cost and requirements

• Time: $O(\log n)$ comparisons.
• Iterative auxiliary space: $O(1)$.
• Requires a monotone condition and efficient access to the midpoint.

A sorted linked list does not provide constant-time midpoint access, so binary search is usually inappropriate even though the values are ordered.

The nonnegative integer hi - lo strictly decreases and after a step is at most half its previous value. Hence at most $\lfloor\log_2 n\rfloor+1$ comparisons for $n\geq1$.

When ordered keys change frequently, a balanced search tree also supports logarithmic updates, predecessors, and ranges.

Generalization

Replace values[mid] < target with the negation of a false-to-true feasibility predicate to search for the first feasible integer, minimum capacity, or transition point. State the interval and postcondition before writing the loop; most binary-search bugs are boundary-contract bugs.

For a predicate feasible(i) that is false then true, the correct replacement is if not feasible(mid): lo = mid + 1, otherwise hi = mid. Using if feasible(mid) with the original branches reverses the meaning. Return hi_initial if no position is feasible. Nonmonotone predicates, unsorted data, or mutation during the search invalidate the invariant; sorting or validating first costs extra and is not part of the logarithmic search.

Run these boundary checks after the definitions above:

assert lower_bound([], 2) == 0
assert lower_bound([2], 2) == 0
assert lower_bound([1, 2, 2, 4], 2) == 1
assert lower_bound([1, 2, 2, 4], 3) == 3
assert lower_bound([1, 2], 0) == 0
assert lower_bound([1, 2], 3) == 2

Source

• Python bisect

My reading · Opened notes are remembered in this browser.