Getting the boundaries right

Two templates cover every binary search you will write: find the first candidate where the predicate is true, or find the last candidate where it is true. Each is a six-line loop. The reason people still get them wrong is that they memorise the six lines instead of the invariant those lines maintain, and a memorised loop cannot be repaired when it hangs.

The invariant is one sentence: the answer is always inside [lo, hi]. Every line below exists to keep that true while shrinking the interval.

First true

def first_true(lo, hi, pred):
    """Smallest x in [lo, hi] with pred(x) true; returns hi if none is."""
    while lo < hi:
        mid = (lo + hi) // 2
        if pred(mid):
            hi = mid          # mid might BE the answer, so keep it
        else:
            lo = mid + 1      # mid is not, and nothing below it is
    return lo

Check both branches against the invariant. If pred(mid) is true then mid is a candidate for the first true, so it must stay in the interval — hence hi = mid and not hi = mid - 1, which throws the answer away whenever mid is exactly the boundary. If pred(mid) is false then by monotonicity everything at or below mid is false too, so all of it leaves at once: lo = mid + 1.

Termination comes from the same arithmetic. While lo < hi, integer division gives mid < hi, because (lo + hi) // 2 <= (hi - 1 + hi) // 2 < hi. So hi = mid strictly lowers hi, and lo = mid + 1 strictly raises lo. The interval shrinks by at least one on every pass and the loop ends with lo == hi.

That mid < hi has a practical payoff: the loop never evaluates pred at hi. So hi can be a sentinel one past the real range — a value that is not a legal candidate — and it will only ever be returned, never probed.

A trace over 12 sorted elements whose first index reaching the target is 7, with lo = 0, hi = 12:

lo	hi	mid	P(mid)	after
0	12	6	false	lo = 7
7	12	9	true	hi = 9
7	9	8	true	hi = 8
7	8	7	true	hi = 7

Four probes for 13 candidates, as predicted: 2⁴ = 16 ≥ 13. Counting probes is counting a loop like any other.

Last true

def last_true(lo, hi, pred):
    """Largest x in [lo, hi] with pred(x) true; returns lo if none is."""
    while lo < hi:
        mid = (lo + hi + 1) // 2      # round UP
        if pred(mid):
            lo = mid                  # mid might BE the answer
        else:
            hi = mid - 1
    return lo

Same invariant, mirrored. A true mid is a candidate for the last true, so it stays: lo = mid. A false mid is out, and so is everything above it: hi = mid - 1.

The + 1 is the whole lesson. Take lo = 4, hi = 5, the last state before the loop ends. Rounding down gives (4 + 5) // 2 = 4, which is lo itself; if pred(4) is true the branch assigns lo = 4, nothing moves, the condition lo < hi still holds, and the process spins forever on one core until the timer kills it. Rounding up gives (4 + 5 + 1) // 2 = 5, so either lo jumps to 5 or hi drops to 4 — the interval shrinks either way.

The rule worth memorising is not "last true uses plus one". It is: the branch that assigns lo = mid must round mid up, and the branch that assigns hi = mid must round it down. Both templates then follow from the invariant rather than from recall.

The first-true and last-true templates on their final two-element interval, showing that the branch which keeps mid decides which way mid rounds100%−+FitSVGEsc

Scroll to zoom · drag to pan · 0 fits · Esc closes

A trace over the same 12 elements, this time for the last index whose value is at most the target, which is 6. The "none is true" sentinel is now one below the range, so lo = -1 and hi = 11:

lo	hi	mid	P(mid)	after
-1	11	5	true	lo = 5
5	11	8	false	hi = 7
5	7	6	true	lo = 6
6	7	7	false	hi = 6

Choosing the initial bounds

Three questions settle lo and hi:

What is the smallest candidate the predicate can be evaluated at? For array indices that is 0. For a rate it is 1 — a rate of zero divides by zero and packs nothing, so it is not a candidate at all.

What is a candidate guaranteed to satisfy the predicate? That is your hi. For a packing rate, the largest pallet works: at that rate every pallet finishes within its hour. hi does not have to be tight — a loose bound costs one or two extra probes out of thirty, and a wrong tight bound costs correctness.

Might no candidate work? Then extend the range by one and use that slot as the sentinel: hi = n for a first-true over indices 0..n-1, or hi = bound + 1 for a value search. With hi = n - 1 the loop must return a real index even when none qualifies, and it hands you n - 1 — an answer that looks plausible and is wrong. One comparison afterwards separates the cases: if lo == n: no answer.

In languages that are not Python, (lo + hi) // 2 overflows a 32-bit signed integer when both are near 2³¹, so C++ and Java want lo + (hi - lo) / 2. Python integers are arbitrary precision, but saying so out loud is free credibility.

Three symptoms, three causes

Binary search bugs are diagnosable from behaviour alone, which makes them fast to fix if you know the mapping.

It hangs. One branch failed to move a pointer. Almost always that is lo = mid paired with a rounded-down mid, and the fix is the + 1; the mirror bug is hi = mid paired with a rounded-up mid.

The answer is off by one. Either you wrote hi = mid - 1 in a first-true loop and discarded the boundary on the pass that found it, or you fed a T T T F F predicate to a first-true loop. Write the predicate out over a small range by hand and compare the strip against the template you used.

It raises an index error. You evaluated the predicate at the sentinel — usually by reading a[lo] after the loop without checking lo < n — or you set hi = n and then used hi as an index somewhere inside the loop body. The loop itself never probes hi; the code around it might.

In an interview

Write the invariant as a comment before the loop: # answer is in [lo, hi]. It takes four seconds, it shows you are deriving rather than recalling, and when you hesitate on a branch you can read the answer off it.

State the sentinel out loud too — "I'll use hi = n so the loop can report that no index qualifies" — because "what if the target isn't there?" is the standard follow-up, and you will have answered it before it was asked.

The mistake that loses points: trying both mid - 1 and mid until the sample input passes. Interviewers watch for this specifically. It says the candidate has no model of why the loop works, so any input outside the samples is a coin flip. Deriving the branch from the invariant takes about the same time and is right on the first attempt.

Check yourself

Your last-true loop hangs on a two-element interval. Name the line and the one-token fix.

mid = (lo + hi) // 2 with lo = mid in the true branch. At lo = 4, hi = 5 the midpoint is 4, so the assignment is a no-op and the interval never shrinks. Change the midpoint to (lo + hi + 1) // 2.

In a first-true search over indices 0..n-1, why is hi = n safe even though n is not a valid index?

Because mid < hi on every iteration, so pred is never called at hi. The value only escapes as the return value, where lo == n is the signal that no index satisfies the predicate.

A search over 13 candidates uses four probes. How many candidates could you handle with ten probes, and what does that say about the growth?

Each probe halves the interval, so ten probes cover 2¹⁰ = 1,024 candidates. Going from 13 to 1,024 costs six extra probes; going from there to 10⁹ costs about twenty more, since 2³⁰ ≈ 1.07 × 10⁹.