Binary Search Without Off-by-One Bugs

Binary search fits in one sentence: look at the middle item, then throw away the half that can't contain what you're looking for. Each step halves the remaining range, so even a billion sorted items need only about 30 steps. That's O(log n); if Big-O is new to you, start with Big-O Notation Explained with Real Code.

Writing it correctly is another story. In Programming Pearls, Jon Bentley reports that when he asked professional programmers to write binary search, about 90% of them had bugs. And the version in Java's standard library had an overflow bug that went unnoticed for about nine years. The usual culprits are off-by-one errors: < or <=? mid or mid + 1? When does the loop stop?

This article gives you one template that answers those questions for you, and shows how far it stretches.

The question to ask#

"Is x in the list?" is the weakest form of binary search. A much more useful question is:

Where is the first item that is greater than or equal to x?

This is usually called lower bound. It answers several questions at once: whether x is present, where it starts if it appears several times, and where you'd insert it to keep the list sorted.

One template: a half-open range#

def lower_bound(a, x):
    """Index of the first item >= x, or len(a) if every item is smaller."""
    lo, hi = 0, len(a)            # invariant: the answer is between lo and hi (inclusive)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < x:
            lo = mid + 1          # a[mid] is too small, so the answer is to its right
        else:
            hi = mid              # a[mid] could be the answer: keep it in range
    return lo

Every line follows from the invariant in the comment:

• hi starts at len(a), not len(a) - 1, because "no item is big enough" is a valid answer.
• If a[mid] < x, then mid and everything before it are too small, so the answer is at least mid + 1.
• Otherwise a[mid] >= x, so mid might be the answer. We can't skip it, so hi = mid, not mid - 1.
• The range shrinks on every pass (mid is always less than hi), so the loop ends. When lo == hi, there's only one candidate left, and that's the answer.

Let's trace a search for 23:

a = [3, 8, 12, 15, 23, 23, 31, 42, 56, 70]
lower_bound(a, 23)   # 4  (the first 23)
lower_bound(a, 20)   # 4  (20 would be inserted before the first 23)
lower_bound(a, 99)   # 10 (bigger than everything: len(a))
lower_bound(a, 1)    # 0

Checking membership is now a one-liner, with no special cases inside the loop:

def contains(a, x):
    i = lower_bound(a, x)
    return i < len(a) and a[i] == x

Upper bound and counting#

Change < to <= and you get upper bound: the first item strictly greater than x.

def upper_bound(a, x):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] <= x:
            lo = mid + 1
        else:
            hi = mid
    return lo

Together they give you the whole block of equal items, so counting duplicates in a sorted list takes O(log n), not O(n):

upper_bound(a, 23) - lower_bound(a, 23)   # 2
a[lower_bound(a, 23):upper_bound(a, 23)]  # [23, 23]

The general version: first True#

Look at the two functions again. All that changes is a test that is False for a while and then True from some point on:

index:      0      1      2      3      4     5     6     ...
a[i] >= 23: False  False  False  False  True  True  True  ...
                                        ↑ the answer

So binary search really finds the boundary of a yes/no question, as long as the answers never flip back from True to False. That's worth its own function:

def first_true(lo, hi, pred):
    """Smallest i in [lo, hi) where pred(i) is True, or hi if there is none.
    pred must be False, False, ..., True, True over that range."""
    while lo < hi:
        mid = (lo + hi) // 2
        if pred(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

lower_bound(a, x) is just first_true(0, len(a), lambda i: a[i] >= x). But the predicate doesn't need an array at all.

Binary search on the answer#

The integer square root of n is the largest r with r * r <= n. In other words, it's one less than the first r where r * r > n:

def isqrt(n):
    return first_true(0, n + 1, lambda r: r * r > n) - 1

isqrt(50)          # 7
isqrt(10**12)      # 1000000, in about 40 steps

This trick solves a whole family of "find the minimum value that works" problems. Say a truck must deliver packages in order, the truck can carry capacity kilograms per day, and everything has to be delivered within days days. What's the smallest capacity that works?

def days_needed(weights, capacity):
    days, load = 1, 0
    for w in weights:
        if load + w > capacity:      # doesn't fit: start a new day
            days, load = days + 1, 0
        load += w
    return days

def min_capacity(weights, days):
    lo, hi = max(weights), sum(weights)
    return first_true(lo, hi, lambda c: days_needed(weights, c) <= days)

min_capacity([3, 2, 2, 4, 1, 4], days=3)   # 6: [3, 2] [2, 4] [1, 4]

Finding the capacity directly is hard, but checking one capacity is easy, and the answer is monotonic: if capacity 6 works, 7 works too. Binary search turns an easy check into a fast search: O(n log S) instead of trying every capacity up to S = sum(weights).

Some boundary details, all following from the template: the capacity can't be below the heaviest package, so lo = max(weights). We pass hi = sum(weights) even though first_true never tests hi itself: if no smaller capacity works, it returns hi, which is correct because carrying everything in one day always works.

The bugs to watch for#

Test it against the slow version#

Binary search is the perfect candidate for a brute-force comparison test: a linear scan is obviously correct, so compare against it on thousands of random inputs, including empty lists and duplicates:

import random

for _ in range(10_000):
    a = sorted(random.randint(0, 20) for _ in range(random.randint(0, 15)))
    x = random.randint(-2, 22)
    expected = next((i for i, v in enumerate(a) if v >= x), len(a))
    assert lower_bound(a, x) == expected, (a, x)

Small values (0–20) force lots of duplicates and edge cases. This kind of test catches every bug in the table above within a fraction of a second.

Recap#

• Ask "where is the first item that is ≥ x?" (lower bound) rather than "is x here?".
• Use a half-open range [lo, hi) with while lo < hi, lo = mid + 1 and hi = mid. Every step shrinks the range, and lo is the answer at the end.
• Binary search finds the boundary of any monotonic yes/no question, so you can search over answers (capacities, sizes, times, commits), not just arrays.
• In Python, reach for bisect first.
• Test against a brute-force version with small random inputs.