BIHZ Coding Lab

Binary search: the three off-by-one traps

Most broken binary searches fail in one of three places: the loop condition, the midpoint, or which half keeps the middle element.

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

Pick one interval convention and keep it for the whole function. With a half-open interval the loop ends when the range is empty and lo is the insertion point.