03 · Discarding possibilities: search and windows

A fast search is not fast because it has two pointers. It is fast because each pointer movement rules out answers without losing a valid one. Two useful examples—binary search and a nonnegative sliding window—look different but share that proof obligation.

Lower bound is a boundary, not necessarily a match

Suppose durations are sorted as [2, 4, 4, 9]. Where should 4 be inserted before all existing fours? At index 1. Where should 5 be inserted? At index 3, even though five is absent. Where should 10 go? At len(a), an insertion boundary, not an index to dereference.

The official bisect_left contract partitions a sorted array into values less than the target and values greater than or equal to it. It locates an insertion point using less-than comparisons rather than searching by equality. We can derive that contract with a half-open unknown region [lo, hi).

Maintain three regions: everything before lo is less than x; everything at or after hi is at least x; the unknown region is in between. At the start both known regions are empty. If the middle value is too small, sortedness rules out the middle and every position before it. Otherwise the middle may be the first qualifying value, so keep its boundary by moving hi to mid, not to mid - 1.

from bisect import bisect_left
from itertools import combinations_with_replacement
 
 
def lower_bound(a, x):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return lo
 
assert lower_bound([2, 4, 4, 9], 4) == 1
assert lower_bound([], 7) == 0
for n in range(8):
    for a in combinations_with_replacement(range(4), n):
        for x in range(-1, 5):
            i = lower_bound(a, x)
            assert i == bisect_left(a, x)
            assert all(v < x for v in a[:i])
            assert all(v >= x for v in a[i:])

The interval shrinks on either branch; when it is empty, the two known regions meet at the answer. For [2, 4, 4, 9] and x = 4, inspect index 2, keep [0, 2), inspect index 1, keep [0, 1), then discard index 0. Both bounds meet at 1. Equal values do not cause a special branch.

Time is O(log n) comparisons and O(1) auxiliary storage, assuming random access and bounded-cost comparisons. Building or sorting the array is separate work. bisect.insort still has O(n) insertion cost in a Python list because elements must move; logarithmic search does not make the whole update logarithmic. Mutation by another thread during search is also outside the library's safety contract. NaN values do not supply the ordinary total ordering this lesson assumes.

A moving window needs an order argument too

Find the length of the shortest nonempty contiguous range with sum at least a positive target. For nonnegative integers, expanding right never decreases the sum; removing a left element never increases it. That monotonicity makes it safe to forget a left boundary after recording a valid window: any future window with that same left boundary is longer, not a better minimum.

from itertools import product
 
 
def shortest_nonnegative(values, target):
    if type(target) is not int or target <= 0:
        raise ValueError("target must be a positive integer")
    if any(type(x) is not int or x < 0 for x in values):
        raise ValueError("values must be nonnegative integers")
    left = total = 0
    best = len(values) + 1
    for right, value in enumerate(values):
        total += value
        while total >= target:
            best = min(best, right - left + 1)
            total -= values[left]
            left += 1
    return 0 if best > len(values) else best
 
 
def brute_shortest(values, target):
    lengths = [
        j - i
        for i in range(len(values))
        for j in range(i + 1, len(values) + 1)
        if sum(values[i:j]) >= target
    ]
    return min(lengths, default=0)
 
assert shortest_nonnegative([2, 3, 1, 2, 4, 3], 7) == 2
for n in range(6):
    for values in product((0, 1, 2), repeat=n):
        for target in range(1, 7):
            assert shortest_nonnegative(values, target) == brute_shortest(values, target)
try:
    shortest_nonnegative([1, -1, 3], 3)
except ValueError:
    pass
else:
    raise AssertionError("negative value accepted")

When the sum first reaches seven on [2, 3, 1, 2], record length four, remove the first two, and stop when the sum drops below seven. Later [4, 3] reaches the target with length two. There are nested loops, but right advances exactly n times and left at most n times across the whole run. Counting movements gives O(n) time including validation, not O(n²). Auxiliary storage is O(1), excluding the input. This implementation expects a finite reusable sequence, not a one-shot generator.

The counterexample is part of the lesson

Remove the validation and try [1, -1, 3], target 3. The usual window reaches total three at the end, records length three, then removes the first one and stops at total two. It never removes the negative one, which would reveal the length-one answer [3]. Removing a left element can now increase the sum, so the reason for stopping no longer holds.

Do not relabel the bug as an edge case and patch one input. The proof's assumption failed. The equality problem in the prefix lesson supports negative numbers, but it answers a different question: counting exact-sum ranges, not finding a shortest range above a threshold. A prefix-sum monotonic deque can solve the latter with negative values; it is outside the implementation verified here.

Likewise, binary search on a numeric answer needs a monotone feasibility predicate, known bounds, and a way to detect impossibility. Small input constraints are a clue to possible methods, not a proof that one particular template is correct.

Exercises

1. Turn lower bound into a membership query without indexing past the end.
2. What two parts of the binary-search predicate change to implement upper bound?
3. Why does the window require a positive target? What should an API specify for target zero?

Exit artifact: trace both algorithms on paper, name the discarded candidates, and explain a counterexample when sortedness or nonnegativity is absent. API references support the library boundary; the window proof is this lesson's derivation, checked by the executed oracle.

Next: Stacks, queues and heaps.