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 loPick 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.