Experiments and implementations · Intermediate

Testing binary-search invariants

Enumerate small sorted inputs and test binary-search boundaries, duplicates and empty arrays through explicit invariants.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Define the returned boundary first
  2. Check the loop invariant explicitly
  3. Enumerate the small boundary cases
  4. Connect tests to the general argument
  5. Ask Logeia about this articleCheck your understanding

Define the returned boundary first

Implement lower_bound in Python 3 as the first position whose value is at least the target. This is a boundary query, not merely a yes-or-no membership test. Duplicates require the leftmost suitable position; when all values are smaller, the answer is the sequence length; the empty sequence returns zero. The candidate interval is half-open, [lo, hi). The algorithm assumes sorted input and does not repair unsorted data before searching, so that precondition remains essential.

Check the loop invariant explicitly

The assertions state that every value before lo is smaller than the target and every value from hi onward is at least the target. When the middle value is smaller, mid itself cannot be the answer, so lo advances to mid plus one. Otherwise mid remains a candidate and hi becomes mid. The assertions deliberately scan slices, adding substantial verification work. Consequently, this instrumented laboratory program is not itself an O(log n) performance implementation.

python
from itertools import combinations_with_replacement
from bisect import bisect_left
def lower_bound(a, target):
    lo, hi = 0, len(a)
    while lo < hi:
        assert all(x < target for x in a[:lo])
        assert all(x >= target for x in a[hi:])
        mid = lo + (hi-lo)//2
        if a[mid] < target: lo = mid+1
        else: hi = mid
    assert all(x < target for x in a[:lo])
    assert all(x >= target for x in a[lo:])
    return lo
cases=0
for length in range(7):
    for values in combinations_with_replacement(range(-2,3),length):
        for target in range(-4,5):
            assert lower_bound(values,target) == bisect_left(values,target)
            cases += 1
print("cases", cases)
assert cases == 4158

Enumerate the small boundary cases

The program enumerates every nondecreasing sequence of length zero through six using values minus two through two, then tests targets minus four through four. It checks 4,158 cases against the standard bisect_left result. Empty sequences, repeated values, endpoint answers and out-of-range targets are included. Enumeration makes small cases reproducible rather than depending on lucky random samples. The invariant assertions also test the meaning of the boundary directly instead of relying only on agreement with another implementation.

Connect tests to the general argument

Exhausting this bounded input set is not a proof over all finite sequences. A general argument establishes the invariant initially, preserves it through both branches, shows that interval width decreases, and derives the desired boundary at termination. Remove the full-slice assertions before evaluating production search complexity, and count comparisons separately if investigating scaling. Floating-point NaNs or unusual comparison functions can violate the ordering assumptions, so they require a carefully specified comparison contract rather than blind reuse of the integer test.

A membership-only test can miss a boundary bug when duplicate targets exist: returning any matching index would pass that weaker test. Validate the actual contract, with all earlier elements smaller and every later element at least the target. The same specification also tests insertion positions for targets absent from the sequence, connecting successful searches and unsuccessful searches through one precise boundary rule.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 10

Choose a learning path