Binary Search, Carefully

Binary search looks like a four-line algorithm and behaves like one of the most bug-prone things you'll ever write. The trick is to fix on one invariant and never violate it.

The invariant

We maintain two pointers, lo and hi. Both refer to positions in the sorted array. The invariant is:

The answer, if it exists, lies in the half-open interval [lo, hi).

That single sentence dictates every decision in the loop.

def lower_bound(arr, target):
    lo, hi = 0, len(arr)          # interval is [lo, hi)
    while lo < hi:                # interval is non-empty
        mid = (lo + hi) // 2      # mid in [lo, hi)
        if arr[mid] < target:
            lo = mid + 1          # answer can't be at mid; shrink left side
        else:
            hi = mid              # answer might be at mid; shrink right side
    return lo                     # smallest index with arr[i] >= target

lower_bound returns the first index whose value is not less than target. If target isn't in the array, it returns the index where target would be inserted to keep the array sorted.

Why it terminates

Every iteration either does lo = mid + 1 or hi = mid. In both cases, hi - lo strictly decreases, so the loop runs at most ⌈log₂ n⌉ times.

Why people get it wrong

The classic bug is mid = (lo + hi) // 2 overflowing in C/C++ when both are near INT_MAX. In Python you don't care, but the safer pattern is lo + (hi - lo) // 2.

The other classic bug: mixing inclusive [lo, hi] and half-open [lo, hi) interval styles in the same function. Pick one and stick to it. I prefer half-open because hi - lo is the size, the empty interval is lo == hi, and the index hi is naturally "one past the end."

When to reach for it

Anywhere you have a monotone predicate over a sorted (or sortable) range — not just literal arrays. "Smallest x such that we can finish in time t" is a binary search. "Largest k such that the answer fits" is a binary search. The structure is always the same: define the predicate, find the boundary.