Binary search

What this chapter covers

Binary search is the payoff for all that sorting. Once an array is sorted, you never have to scan it again: to find anything, look at the middle, and throw away the half that can't contain it. Repeat, and each step halves what's left, so a billion elements take about thirty comparisons instead of a billion. This chapter builds the classic search and the two variants that matter more in practice — lower_bound and upper_bound, which find where a value would go — and confronts binary search's dirty secret: it's one of the most bug-prone algorithms in computing, and getting the boundaries exactly right is the whole skill.

A bit of history

The idea of binary search is old — it's how you look up a word in a dictionary or a name in a phone book — but the correct algorithm was startlingly hard to pin down. John Mauchly described it in 1946, yet the first published binary search with no bugs didn't appear until 1962; the versions in between had off-by-one errors and boundary mistakes. Jon Bentley, in his 1980s "Programming Pearls," reported that when he asked professional programmers to write a binary search, roughly 90% produced buggy code — even given hours and a compiler. And in 2006 a subtle integer-overflow bug was found in the binary search that had shipped in the Java standard library, textbooks, and Bentley's own code for two decades. So binary search is the algorithm that humbles everyone: trivial to describe, treacherous to implement, which is exactly why it's worth building carefully by hand once.

The intuition

You have a sorted array and want to know if it contains some target. Look at the middle element. If it's the target, done. If the target is smaller, it can only be in the left half — so discard the right half entirely, and repeat on the left. If it's larger, discard the left. Each comparison throws away half of what remains, so the number of comparisons is the number of times you can halve n before nothing is left: log₂ n.

The plain search answers "is it here, and where?" But the more useful question is often "where would it go?" — and that's lower_bound: the first position whose element is not less than the target, which is exactly where you'd insert the target to keep the array sorted. It works whether or not the target is present, the returned index tells you how many elements are smaller (a range query for free), and paired with upper_bound it brackets every copy of a duplicated value. Real code uses these boundary searches far more than the present-or-not one, which is why bisect exposes them and not a plain "find."

Complexity: how it scales

Binary search is $O(\log n)$ time and $O(1)$ space — a window that halves each step, tracked by two integers. Its one hard precondition is that the input is sorted; on unsorted data it returns nonsense, silently. The chart runs many searches over sorted arrays of growing size, comparing binary search and bisect against a linear scan:

The linear scan climbs with n — it's O(n) per query — and drops off the chart past ten thousand elements because it becomes unbearable. The two binary searches stay almost flat: growing the array a hundredfold adds only a handful of probes per search. That gap between a line that grows and a line that barely moves is the entire argument for sorting your data.

What it's good at, what it isn't

Binary search is the right tool whenever you have sorted data and search it more than once. The sort is an up-front cost, O(n log n), but every search afterward is O(log n) instead of O(n), so it pays off fast for any read-heavy workload — a lookup table, a sorted index, a config you query repeatedly. And lower_bound turns a sorted array into a tiny database: insertion points, rank queries, range counts, and nearest-neighbor lookups all fall out of it.

Where it's the wrong tool is unsorted or fast-changing data. If the data isn't sorted, you'd pay O(n log n) to sort before you could search — and if you only search once, a plain O(n) scan is cheaper. If the data changes constantly, keeping the array sorted costs O(n) per insertion (shifting elements), which usually loses to a balanced tree or a hash table. And when you just need membership with no order or range queries, a hash set's O(1) beats binary search's O(log n). Binary search shines specifically on data that's sorted, large, and queried often.

The data, or the inputs

The face-off searches sorted arrays of even numbers (so about half the targets are misses, the worst case for the search). The animation searches a 21-element sorted array for the value 30, recording the window at each probe so you can watch it collapse.

Build it, one function at a time

The classic search — halve the window until the target is found or the window is empty:

def binary_search(values, target, probe=None):
    """O(log n): keep a window [lo, hi); look at the middle; throw away the half that
    can't contain the target. Returns the index of `target`, or -1. The input MUST be
    sorted — that's the precondition the whole method rests on."""
    lo, hi = 0, len(values)
    while lo < hi:
        mid = (lo + hi) // 2
        if probe is not None:
            probe.append({"lo": lo, "hi": hi, "mid": mid})
        if values[mid] == target:
            return mid
        if values[mid] < target:
            lo = mid + 1          # target is in the right half
        else:
            hi = mid              # target is in the left half
    return -1

Lower bound — the first index whose element is at least the target, i.e. the insertion point. Note it has no early return: it always narrows to a single position, which is what makes it work whether or not the target is present:

def lower_bound(values, target, probe=None):
    """O(log n): the index of the FIRST element >= target — where target would be
    inserted to keep the array sorted (this is bisect_left). More useful than plain
    search: it works whether or not target is present, and the returned index equals
    the number of elements strictly less than target — a range query for free."""
    lo, hi = 0, len(values)
    while lo < hi:
        mid = (lo + hi) // 2
        if probe is not None:
            probe.append({"lo": lo, "hi": hi, "mid": mid})
        if values[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo

Upper bound — the first index strictly greater than the target; with lower_bound it brackets every copy:

def upper_bound(values, target):
    """O(log n): the index of the first element > target (bisect_right). Together with
    lower_bound it brackets every copy of target: the equal elements are exactly the
    slice values[lower_bound : upper_bound]."""
    lo, hi = 0, len(values)
    while lo < hi:
        mid = (lo + hi) // 2
        if values[mid] <= target:
            lo = mid + 1
        else:
            hi = mid
    return lo

Watch it work

Here's binary search hunting for 30 in a 21-element sorted array. Blue is the live window — where the target might still be; orange is the middle element being checked; dark cells have been discarded. Step through it and watch the blue window halve on every single probe: the search looks at the middle, compares, and throws away half the array, so a 21-element search finishes in just 5 probes. Picture the array a thousand times bigger and the window would still collapse in about ten more steps — that's the logarithm at work:

The complete code

Both versions in one place — flip between them. The from-scratch tab has the search and both bounds. The library tab is bisect: bisect_left is our lower_bound and bisect_right is our upper_bound, both in C. Notice bisect has no plain "find" — you build it from bisect_left, because the boundary searches are the primitive.

"""Binary search — find an element in a sorted array in O(log n) by repeatedly
halving the search window. It's the payoff for all that sorting: once data is sorted,
you never scan it again.

Beyond the textbook "is it present?" search, the two variants that matter in practice
are lower_bound and upper_bound — they find where a value WOULD go, which works whether
or not it's present and answers range queries. They're the operations behind Python's
`bisect` module, and getting their boundaries exactly right is famously fiddly, which
is why it's worth building them once by hand.
"""


# region: binary_search
def binary_search(values, target, probe=None):
    """O(log n): keep a window [lo, hi); look at the middle; throw away the half that
    can't contain the target. Returns the index of `target`, or -1. The input MUST be
    sorted — that's the precondition the whole method rests on."""
    lo, hi = 0, len(values)
    while lo < hi:
        mid = (lo + hi) // 2
        if probe is not None:
            probe.append({"lo": lo, "hi": hi, "mid": mid})
        if values[mid] == target:
            return mid
        if values[mid] < target:
            lo = mid + 1          # target is in the right half
        else:
            hi = mid              # target is in the left half
    return -1
# endregion


# region: lower_bound
def lower_bound(values, target, probe=None):
    """O(log n): the index of the FIRST element >= target — where target would be
    inserted to keep the array sorted (this is bisect_left). More useful than plain
    search: it works whether or not target is present, and the returned index equals
    the number of elements strictly less than target — a range query for free."""
    lo, hi = 0, len(values)
    while lo < hi:
        mid = (lo + hi) // 2
        if probe is not None:
            probe.append({"lo": lo, "hi": hi, "mid": mid})
        if values[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo
# endregion


# region: upper_bound
def upper_bound(values, target):
    """O(log n): the index of the first element > target (bisect_right). Together with
    lower_bound it brackets every copy of target: the equal elements are exactly the
    slice values[lower_bound : upper_bound]."""
    lo, hi = 0, len(values)
    while lo < hi:
        mid = (lo + hi) // 2
        if values[mid] <= target:
            lo = mid + 1
        else:
            hi = mid
    return lo
# endregion

"""Python's `bisect` module is binary search done right — `bisect_left` is our
lower_bound, `bisect_right` is our upper_bound, both in C. It's the standard way to
search a sorted list and to keep a list sorted as you insert (`insort`). There's no
plain "find the index of x" in bisect; you build it from bisect_left, exactly as below.

The face-off is our binary search against `bisect` and against a linear scan — the
O(log n) vs O(n) gap that is the whole reason to keep data sorted.
"""
import bisect


# region: bisect_lib
def search_bisect(values, target):
    """Locate target via bisect_left, then confirm it's actually there."""
    i = bisect.bisect_left(values, target)
    return i if i < len(values) and values[i] == target else -1


def lower_bound_bisect(values, target):
    return bisect.bisect_left(values, target)


def upper_bound_bisect(values, target):
    return bisect.bisect_right(values, target)
# endregion


# region: linear
def linear_search(values, target):
    """The O(n) baseline: scan until found. This is what binary search replaces —
    and the reason the difference is worth a sort."""
    for i, v in enumerate(values):
        if v == target:
            return i
    return -1
# endregion

Scratch vs library

Both binary searches are O(log n), so the gap is the usual constant. Two thousand searches over a million-element array took our binary search about 2.8 ms and bisect about 0.66 ms — bisect roughly four times faster, being C over Python. But hold that next to the linear scan, which isn't even on the chart past ten thousand elements because O(n) per query becomes unusable. That's the comparison that matters: binary search versus bisect is a constant factor; binary search versus linear is a complexity-class chasm, O(log n) against O(n). The right lesson isn't "use bisect because it's faster than my code" (though you should) — it's "search sorted data with a logarithm, never a scan."

Where you'll actually meet it

Binary search is everywhere data is sorted. bisect.insort keeps a list ordered as items arrive; databases binary-search within the sorted pages of a B-tree index (a later chapter); git bisect binary-searches your commit history to find the one that introduced a bug; version resolvers binary-search for compatible releases. Any autocomplete or range filter over sorted data uses lower/upper bound. And "binary search on the answer" quietly optimizes everything from rate limiters to scheduling. The plain array search is just the most visible member of a family that shows up any time a problem has a sorted structure to exploit.

Takeaways

Binary search finds an element, or its insertion point, in a sorted array in $O(\log n)$ by halving the search window each step — the reason a one-time sort pays for itself across many searches. The boundary variants, lower_bound and upper_bound, are the workhorses: they locate where a value belongs whether or not it's present and answer range queries for free. Its precondition (sorted) and its notorious boundary bugs are the two things to respect — which is a fine reason to reach for bisect.

One chapter remains in the tier, and it's a beautiful twist on sorting. Quickselect finds the k-th smallest element — the median, a percentile, the top-k threshold — in $O(n)$ without sorting the array at all, by reusing quicksort's partition and recursing into only the side that contains the answer. It's the last idea in the recursion-and-sorting arc, and it closes it by showing that sometimes you don't need the whole sorted order to find what you're looking for.