Off-by-one traps

Almost every binary search bug is an off-by-one error. The window starts one position too wide, the loop stops one step too early, or a pointer does not move. You can avoid all of them with one convention, one rounding rule and a short checklist.

Pick one convention

You have seen two kinds of window. Each one works correctly on its own. Most bugs happen when code mixes a line from one kind with a line from the other.

Choose one for each problem, write a comment saying which one you chose, and check every line against its column.

The lo = mid trap

Here is a search for the first T that looks correct but is broken. It uses lo = mid where it should use lo = mid + 1:

lo, hi = 0, len(a) - 1
while lo < hi:
    mid = (lo + hi) // 2
    if a[mid] < t:
        lo = mid          # should be mid + 1
    else:
        hi = mid

With a large window it seems to work. The problem appears when only two positions are left, so hi == lo + 1. Then mid = (lo + lo + 1) // 2 = lo, because // rounds down. If a[mid] < t, the update sets lo to the value it already has. Nothing changes, so the loop runs forever. Step through it below, then switch to the fixed version.

In the terms of lesson 2, the invariant is fine here. What fails is the proof that the loop stops: the window does not get smaller when mid == lo. That is why the checklist below asks you to test a two-element window by hand.

Rounding mid up

Sometimes lo = mid is exactly right. When you search for the last T in T … T F … F, a T at mid might be the answer, so lo must keep it. In that case, make mid round up, so that it can never equal lo:

def last_true(lo, hi, ok):
    """Largest x in [lo, hi] with ok(x), given ok(lo) is True."""
    while lo < hi:
        mid = (lo + hi + 1) // 2   # rounds up: lo < mid <= hi
        if ok(mid):
            lo = mid               # mid may be the last T: keep it
        else:
            hi = mid - 1           # mid is F: drop it
    return lo

The whole-number square root from the last lesson is last_true(0, n, lambda r: r * r <= n).

A checklist for every search

1. Write the invariant. What do lo and hi mean? For example: “every index before lo is F, and every index from hi onwards is T”. You can check a sentence like that.
2. Check the start. Do the first values of lo and hi make the invariant true, even when the answer is “none”? (For example, hi = len(a), not len(a) - 1.)
3. Check each branch. Does it keep the invariant true, given what the comparison just told you about mid?
4. Check that the window shrinks. Try a two-element window by hand. Does every branch make it smaller?
5. Check the end. When the loop stops, what does lo mean? Do you still need to check that it is inside the list, or that it equals the target?
6. Test the edge cases: lists of length 0, 1 and 2; the target at the first and last position; and a missing target that is smaller than all the values, between two values, or larger than all the values.

A note on overflow

Python integers have no maximum size, so (lo + hi) // 2 is always safe in Python. In C, C++ and Java, lo + hi can be larger than the biggest allowed int when both are above about 1.07 billion. The result wraps around and mid becomes negative. In 2006, Joshua Bloch reported that the binary search in Java’s standard library had had this bug for about nine years. The usual fix is mid = lo + (hi - lo) / 2. You don’t need it in Python, but you will need it when you write the same loop in another language.