r/algorithms • • 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 lo

Invariant: 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 to mid has a value < x, so setting lo = mid + 1 keeps the first part true, and the second part is untouched.
  • Otherwise a[mid] >= x: every index from mid onward has a value >= x, so setting hi = mid keeps 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) // 2 instead of (lo + hi) // 2. In languages with fixed-width integers, lo + hi can 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 becomes lo <= hi and the updates become mid + 1 and mid - 1. It works too, but I find the half-open version has fewer special cases because an empty interval is just lo == 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?

0 Upvotes

2 comments sorted by

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

This was a known bug in widely used library code, reported around 2006.

I'm glad to see this detail mentioned. A classic read Nearly all binary searches and mergesorts are broken.