Repair binary-search boundary contracts

Understand the likely causes

• Closed and half-open interval formulas were mixed, or one branch fails to remove a tested impossible candidate.
• The API returns an insertion point but callers interpret every returned position as a successful equality match. The source may also have become unsorted after preprocessing.

Name the result and accepted sequence first

Decide whether the function promises any matching occurrence, the first equal value, or a lower-bound insertion position. Those are different contracts when duplicates or absence occur. Record the comparison key and confirm the sequence is sorted under that exact relation. Do not repair loop arithmetic while ignoring an unsorted fixture, a changed key, or mutation during search. Use a tiny synthetic sequence and preserve the failing target. The expected answer should follow from the contract rather than from the output of the currently defective implementation.

Draw the known and unknown regions

For lower bound, choose [lo,hi) as unknown, all earlier values less than target, and all positions at or beyond hi at least target. A midpoint smaller than target is definitely excluded, so lo becomes mid+1. Otherwise the midpoint can still be the answer, so hi becomes mid. Before each iteration write the width hi-lo and verify it strictly decreases after either branch. A closed interval uses another invariant and termination condition; borrowing one of its updates without its proof can create an endless two-element case.

Instrument progress without changing the result contract

The program records only interval boundaries and asserts strict progress. Its trace exposes the chosen invariant while keeping the algorithm independent of real application data. For target3, the duplicate block begins at1. The final answer can equal len(values), so a caller must still check bounds and equality before reporting membership. Keep that membership check outside the lower-bound contract instead of returning a fabricated matching index. The assertion is a diagnostic aid; the partition and shrinking-width argument explain why it should hold for every accepted iteration.

def traced_lower_bound(values, target):
    lo, hi = 0, len(values)
    trace = []
    while lo < hi:
        trace.append((lo, hi))
        width = hi - lo
        mid = lo + width // 2
        if values[mid] < target:
            lo = mid + 1
        else:
            hi = mid
        assert hi - lo < width
    return lo, trace

print(traced_lower_bound([1, 3, 3, 8], 3))
position, _ = traced_lower_bound([1, 3, 3, 8], 9)
print(position)

(1, [(0, 4), (0, 2), (0, 1)])
4

Verify partition properties rather than one lucky answer

Enumerate small sorted arrays with duplicates and compare against bisect_left or a simple linear reference. For each returned p, check every value before p is smaller and every value from p onward is at least target. Include empty and singleton input, all-equal values, a target below all values, a gap, and a target above all values. Separately test the caller’s membership branch and any promised duplicate policy. Do not hide the defect by imposing an arbitrary iteration cap that returns an unproved midpoint when the cap is reached.

Keep it from recurring

• Document one interval convention and result type per function. Keep sortedness ownership, duplicate behavior, and membership conversion explicit, and preserve the minimal two-candidate regression fixture.