What makes it safe to throw half away? | DSA & Design, Connected

Picture

Binary search is not fundamentally about the middle of an array. It is about a boundary: once a condition becomes true, it stays true. Checking the middle tells you which part cannot contain the first true position. An invariant is the promise that remains true after every update.

Predict

Can you binary-search the first True in [False, True, False, True] using the usual boundary algorithm?

Reveal the reasoning

No. A false result in the middle does not prove there was no true result earlier. The condition needs a false-then-true shape. Sorting is one way to create such a condition, but monotonic feasibility can provide it too.

Go deeper: state the promise before the loop

Find the first array position whose value is at least target, assuming ascending order. Keep the candidate boundary in [lo, hi], with len(values) representing “none.” Everything before lo is too small; everything at or after hi is large enough, when such positions exist.

def lower_bound(values, target):
    lo, hi = 0, len(values)
    while lo < hi:
        mid = (lo + hi) // 2
        if values[mid] >= target:
            hi = mid
        else:
            lo = mid + 1
    return lo

assert lower_bound([2, 4, 4, 9], 4) == 1
assert lower_bound([2, 4, 4, 9], 10) == 4
assert lower_bound([], 3) == 0

Trace for target 4: (lo, hi) goes (0, 4) → (0, 2) → (0, 1) → (1, 1). Each move preserves the boundary promise and shrinks the range. That explains both correctness and termination. The algorithm takes O(log n) comparisons and O(1) extra space.

Recognition transfer: if a delivery capacity C is sufficient, every larger capacity is also sufficient under fixed rules. You may binary-search the minimum sufficient capacity, provided you can correctly check feasibility and establish a bounded search range. Total time also includes each feasibility check.

Analogy limit: “seems ordered” is insufficient. You must justify the predicate’s monotonicity.

Change one rule

You seek a capacity that is sufficient but also pays a discount only at selected values. Can you binary-search “sufficient and discounted”?

Check the variation

Not without another monotonicity argument. Capacity sufficiency may stay true while discount eligibility flips back and forth.

Connect

Windows also discard possibilities using a monotonicity argument. Greedy proofs justify permanent choices. A BST supports eliminating subtrees using its ordering invariant.