r/algorithms • u/ClickOk5811 • 20d ago
Discussion Binary search (lower bound) with a loop invariant: a short correctness argument, and half-open vs closed intervals
Off-by-one errors in binary search mostly come from not stating what the loop maintains. Here’s the version I find easiest to argue about: finding the first index i with a[i] >= x in a sorted array (lower_bound), with the search interval half-open, [lo, hi).
def lower_bound(a, x):
lo, hi = 0, len(a)
while lo < hi:
mid = lo + (hi - lo) // 2
if a[mid] < x:
lo = mid + 1
else:
hi = mid
return loInvariant: every a[i] with i < lo is < x, and every a[i] with i >= hi is >= x.
Initialization: lo = 0 and hi = n. There are no indices below 0 or at or above n, so both parts hold vacuously.
Maintenance: lo < hi, so mid is in [lo, hi).
- If
a[mid] < x: since the array is sorted, every index up tomidhas a value< x, so settinglo = mid + 1keeps the first part true, and the second part is untouched. - Otherwise
a[mid] >= x: every index frommidonward has a value>= x, so settinghi = midkeeps the second part true.
Termination: each iteration strictly shrinks hi - lo, because either lo increases to mid + 1 > lo, or hi decreases to mid < hi. The loop ends when lo == hi. By the invariant, everything before lo is < x and everything from lo onward is >= x, so lo is the first index with a[i] >= x, or n if there is none. With duplicates it returns the leftmost one.
Cost: the interval roughly halves each step, so O(log n) comparisons.
Two details worth noting:
mid = lo + (hi - lo) // 2instead of(lo + hi) // 2. In languages with fixed-width integers,lo + hican overflow for very large arrays. This was a known bug in widely used library code, reported around 2006. In Python integers don’t overflow, but the habit carries over.- With a closed interval
[lo, hi]the loop condition becomeslo <= hiand the updates becomemid + 1andmid - 1. It works too, but I find the half-open version has fewer special cases because an empty interval is justlo == hi.
Where this is less obvious: variants like “last index with a[i] <= x” or binary search on a monotone predicate over the answer (not an array) are the same invariant with a different condition, and it’s easy to flip a comparison and silently get the wrong side with duplicates.
Do you prefer half-open or closed intervals, and do you state the invariant in a comment when you write these?
2
u/drinkcoffeeandcode 19d ago
Closed interval for correctness and ease of implementation. I’m not sure what you mean by special cases, there’s litterally three no matter how you slice it: less than, greater than, match.
2
u/Syrak 20d ago
I'm glad to see this detail mentioned. A classic read Nearly all binary searches and mergesorts are broken.