Binary search, and why it is hard to get right

Binary search runs in $O(\log n)$ time, but the off-by-one bugs are famous.

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

The invariant: the answer is always in the half-open range $[lo, hi)$.