Skip to main content

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.

Lower bound​

This implementation returns the first position whose value is at least the target, using the half-open interval [lo,hi)[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

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)O(\log n) comparisons.
  • Iterative auxiliary space: O(1)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.

Generalization​

Replace values[mid] < target with any monotone 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.

Source​