The predicate, not the array

"Find a value in a sorted array" is one use of binary search, not a definition of it, and taking it for the definition costs you every problem where nothing is sorted. The algorithm needs one thing: a yes/no question over an ordered range of candidates whose answer, once it turns true, never turns back.

Write that question down and the rest is a template. Fail to write it down and you are guessing at lo and hi until the examples pass.

Monotone is the whole precondition

A predicate P over candidates x is monotone when P(x) implies P(y) for every y > x. Evaluate it across the range and you get a strip of falses followed by a strip of trues:

x:     0  1  2  3  4  5  6  7  8  9 10 11
P(x):  F  F  F  F  F  F  F  T  T  T  T  T

There is exactly one place where it flips, and that place is the answer. Binary search does not find a value; it finds that boundary. Each probe reads one cell and throws away half the strip, so a range of 10⁹ candidates costs about 30 probes — 2³⁰ is 1,073,741,824, just over 10⁹ — instead of 10⁹ reads.

A monotone predicate as a strip of false cells followed by true cells, with lo, mid and hi markers and the boundary at the first true100%−+FitSVGEsc

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

The sorted array is one predicate among many

For a non-decreasing array and a target, take P(i) = a[i] >= target. Sortedness makes it monotone: if a[i] already reaches the target, everything to the right is at least as large. The boundary is the first index that reaches the target.

def lower_bound(a, target):
    lo, hi = 0, len(a)              # hi = len(a) means "no such index"
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] >= target:        # P(mid)
            hi = mid
        else:
            lo = mid + 1
    return lo

Nothing outside the if mentions the array. Swap that one line for a different monotone question and the rest of the function is untouched — which is the point of learning the shape rather than the special case. The mechanics of lo, hi and the + 1 are in getting the boundaries right; here we only care about what goes inside the if.

Three predicates that have no array to sort:

• P(r) — "a packer working at r cartons an hour clears every pallet before the shift ends". Monotone because working faster never takes longer.
• P(t) — "by minute t, at least k machines have finished". Monotone because a machine that has finished stays finished.
• P(d) — "the fleet can be split into at most m routes if no route is longer than d". Monotone because a longer allowance never forces more routes.

None of these is a lookup. Each is a computation you run on demand, and the candidates are numbers you never store. That is binary search on the answer, and it is the more common form in interviews.

Say the precondition out loud

Before writing lo and hi, say the sentence: "P is monotone in x because increasing x only relaxes the constraint." Every legitimate use of binary search has some version of that sentence, and it is usually one line long:

• more speed never adds hours
• a later deadline never rules out a plan that already fit
• a larger capacity never forces an extra bin
• a bigger index in a sorted array never holds a smaller value

If you cannot produce that line, you do not yet know whether the technique is legal. This is the same precondition check that step 4 of the solving loop asks for, and binary search is where skipping it hurts most.

When monotonicity fails, the search lies quietly

A machine packs faster as you raise its rate, but above rate 4 it overheats and stalls for a cooldown, so it misses the deadline again. Feasible rates over 1 to 16 are 2, 3 and 4 only:

r:     1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
P(r):  F  T  T  T  F  F  F  F  F  F  F  F  F  F  F  F

Run the first-true template with lo = 1 and hi = 17, one past the range, so that 17 means "nothing works". First probe: mid = (1 + 17) // 2 = 9, P(9) is false, so lo = 10 — and all three feasible rates were in the half just thrown away. The remaining probes at 13, 15 and 16 are false too, the loop ends with lo = 17, and the function reports that no rate clears the shift.

Nothing raised an exception. No index went out of range. The code is the same code that is correct on a monotone predicate, the tests you wrote from the examples may well pass, and the answer is wrong. Binary search cannot detect that its precondition is violated, which is exactly why you have to check it yourself. For a two-sided shape like this one, the tool is a scan, a sort by a different key, or a ternary search on a unimodal function — not this.

In an interview

You are being tested on whether you can name the search space and justify it, not on whether you can type the loop. Lead with the predicate: "The candidates are the rates from 1 to the largest pallet. P(r) is 'rate r finishes in time'. It is monotone because packing faster never takes longer, so the rates read F F F T T T and I want the first T. That is about 30 probes over a range of 10⁹."

That is four sentences and it settles correctness, legality and complexity before any code exists. Compare it with "the array is sorted, so binary search", which says nothing when the array is not the thing being searched.

The mistake that loses points: asserting monotonicity instead of arguing it. An interviewer who hears "it's monotone, so I'll binary search" will ask why, and "because the answers look sorted" is the answer of someone who pattern-matched. The reason always names a direction — more of x only ever helps — and if you cannot name one, the honest move is to say the predicate is not monotone and pick a different tool.

Check yourself

The candidates run from 1 to 10⁹ and each check costs one pass over n = 10⁴ items. How many operations, and how does that compare with trying every candidate?

About log₂(10⁹) ≈ 30 probes at 10⁴ each: 30 × 10⁴ = 3 × 10⁵ operations. Trying every candidate is 10⁹ × 10⁴ = 10¹³, which is about 3 × 10⁷ times more work.

In a non-decreasing array you want the last index whose value is at most the target. Write the predicate and say whether it is monotone.

P(i) = a[i] <= target is true on a prefix and false afterwards — T T T F F — so it is monotone in the reverse direction. Either search for the last true, or flip it to Q(i) = a[i] > target, find the first true, and subtract 1. What you must not do is feed a T T T F F strip to a first-true loop.

A colleague's binary search returns "no feasible value" on an input where three values are feasible. What single question do you ask about their predicate?

Is it monotone? A false report of "no answer" is the signature of a true block that sits entirely inside a half the search discarded. The loop cannot detect this, so the bug is in the precondition, not in the boundaries.