Inspect the middle value of a sorted array to decide which half can contain the target. Each comparison discards half the candidates.

A binary-search simulator showing lo, mid, hi, and the shrinking candidate interval

Change the target or pick an existing array value, then play. Faded cells have already been eliminated.

TimeO(log n)

RequirementSorted array

1 million valuesAt most 20 comparisons

1 billion valuesAt most 30 comparisons

Three forms of binary search

Exact search stops at a matching value. Lower bound returns the first position with a value at least x; upper bound returns the first value greater than x. Their difference counts occurrences of x. Try both with Many duplicates. In Python, bisect_left(a, x) is lower bound and bisect_right(a, x) is upper bound.

Choose one boundary convention

Exact search here uses the closed interval [lo, hi] with lo <= hi; lower and upper bounds use the half-open interval [lo, hi) with lo < hi. Mixing conventions can cause infinite loops or off-by-one errors.

Parametric search: binary-search the answer

For a largest or smallest feasible value, define a predicate that checks a proposed answer x. If feasibility changes only once as x increases, binary search locates that boundary. Typical examples include cutting cables, choosing a saw height, and placing routers.

lo, hi = 1, max(a)          # possible answers
while lo <= hi:
    mid = (lo + hi) // 2
    if ok(mid):             # mid is feasible
        ans = mid
        lo = mid + 1        # try a larger answer
    else:
        hi = mid - 1