Binary search — including on the answer space

The vocabulary, defined once

Binary search has a small, fixed cast of characters. Pin down each one and the code stops looking like a puzzle. The plain-English on-ramp is the only idea you truly need: you keep a window of "where the answer could still be," and on every step you look at the middle of that window and throw away the half that can't contain the answer. Half gone, every step. That repeated halving is what makes it fast.

• Binary search — an algorithm that locates a target in a structure with a known order by repeatedly halving the region still under consideration. "Binary" = two halves; each comparison discards one of them.
• Sorted invariant — the standing assumption that the data is in order (ascending here). An invariant is a fact that stays true the whole time the algorithm runs. Binary search is only correct while this holds, because "throw away the left half" relies on every element there being smaller than the target.
• lo / hi / mid — three index variables. lo is the low end of the current window, hi is the high end, and mid is the midpoint between them that we probe each step. The window [lo, hi] always contains the answer (that's the second invariant); we shrink it until only one cell is left.
• Loop bound (lo <= hi vs lo < hi) — the condition that keeps the loop going. lo <= hi is used when you might accept the cell lo == hi as the answer inside the loop (classic "find this exact value, return its index or -1"). lo < hi is used when the loop's job is to converge two pointers onto a single surviving cell, and you read off lo after the loop (the "first-true" style below). Mixing the bound up with the wrong update rule is the #1 source of bugs.
• mid = lo + (hi - lo) // 2 — the safe way to compute the midpoint. The naive (lo + hi) // 2 is mathematically identical but can overflow in fixed-width-integer languages: if lo and hi are both near the maximum integer, their sum wraps past it and goes negative. Computing the gap hi - lo first (always smaller than hi) and adding half of it to lo can never overflow. Python ints are unbounded so it's only style there, but it's the right reflex everywhere.
• O(log n) — "logarithmic time." The number of steps grows like the logarithm of the input size n. Concretely: each step halves the window, so the count of steps is "how many times can you halve n before reaching 1," which is log₂ n. A million elements → ~20 steps; a billion → ~30. Doubling n adds exactly one step.
• Binary search on the answer — the interview twist. Instead of an array, you bisect a range of candidate answers, asking a yes/no question at each midpoint. Covered in depth below.
• Monotonic predicate — a yes/no test f(k) whose answers, read left to right across the candidates, look like F F F T T T (or T T T F F F): once it flips, it never flips back. Monotonic means "moves in one direction only." This single flip point is exactly what binary search hunts for.
• lower_bound / upper_bound — named boundary searches. lower_bound(x) returns the index of the first element >= x (the leftmost spot x could be inserted while staying sorted). upper_bound(x) returns the first element strictly > x. Both are just first-true bisection with predicates a[k] >= x and a[k] > x; their difference (upper - lower) is the count of elements equal to x.

A traced search, indices and all

The plain-English walkthrough above showed values; here's the same kind of search written as an interviewer expects — exact lo, mid, hi at every step. We search for 9 in the 8-element array [1, 4, 5, 7, 9, 11, 13, 16] (indices 0–7), using the inclusive bound lo <= hi and returning the index where we find it:

# array:   index  0  1  2  3  4   5   6   7
#          value  1  4  5  7  9  11  13  16        target = 9
#
# start    lo=0  hi=7   mid = 0 + (7-0)//2 = 3   a[3]=7   7 < 9  -> go right: lo = mid+1 = 4
# step 2   lo=4  hi=7   mid = 4 + (7-4)//2 = 5   a[5]=11  11 > 9 -> go left:  hi = mid-1 = 4
# step 3   lo=4  hi=4   mid = 4 + (4-4)//2 = 4   a[4]=9   9 == 9 -> FOUND at index 4

Read down the mid column: 3, 5, 4 — three probes to pin one of eight cells, just as log₂ 8 = 3 promises. Notice how the window [lo, hi] shrinks ([0,7] → [4,7] → [4,4]) and how each update steps past the rejected mid (mid+1 or mid-1), never re-examining it. That "step past mid" is what guarantees the window strictly shrinks. Here is the same logic as runnable code, the inclusive-bound form for finding an exact value:

def search(a, target):
    lo, hi = 0, len(a) - 1      # window is the whole array, inclusive both ends
    while lo <= hi:                # <= : a single-cell window lo==hi is still worth checking
        mid = lo + (hi - lo) // 2  # overflow-safe midpoint
        if a[mid] == target: return mid
        if a[mid] < target:  lo = mid + 1  # answer is strictly right of mid
        else:                hi = mid - 1  # answer is strictly left of mid
    return -1                    # window emptied (lo > hi): target absent

The infinite-loop trap

Every binary-search bug is the same bug wearing a different hat: the window stops shrinking, so the loop spins forever (or, the mirror image, it shrinks one cell too far and skips the answer). The trap appears when the midpoint can equal one of the endpoints and your update rule then fails to move that endpoint. Concrete failure with the lo < hi bound:

# BUGGY — hangs when hi = lo + 1
while lo < hi:
    mid = lo + (hi - lo) // 2   # with lo=3, hi=4 -> mid = 3 (floor)
    if f(mid): lo = mid           # BUG: lo = 3 again -> no progress, loop forever
    else:      hi = mid - 1

When hi = lo + 1, floor division makes mid == lo. Setting lo = mid writes lo back to itself and nothing changes. The cure is to pair the rounding of mid with the update that always advances. Two clean, memorizable pairings:

Rule of thumb: if an update can leave a pointer on mid, round mid toward the other pointer so the gap is forced to close. The inclusive lo <= hi form sidesteps this entirely, because both of its updates (mid + 1 and mid - 1) always step past mid. The template below uses the half-open lo < hi form correctly: floor mid is paired with lo = mid + 1, so it can never stall.

The harder version isn't searching a sorted array — it's searching the answer. "Smallest k such that f(k) is true" where f is monotonic.

def first_true(lo, hi, f):
    # invariant: f(hi) is True; want smallest k with f(k) True
    while lo < hi:
        mid = (lo + hi) // 2
        if f(mid): hi = mid
        else:      lo = mid + 1
    return lo

function firstTrue(lo:number, hi:number, f:(k:number)=>boolean): number {
  while (lo < hi) {
    const mid = (lo + hi) >>> 1;
    if (f(mid)) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

Trace why this template terminates: mid is the floor of the midpoint, so when hi = lo + 1 we get mid = lo. The true branch sets hi = mid = lo, ending the loop; the false branch sets lo = mid + 1 = hi, ending the loop. Either way the gap closes — no stall. This is the floor-mid-with-lo = mid + 1 pairing from above. The returned lo is the first index where f is true: every candidate below it was proven false, every candidate at or above it inherits truth from monotonicity. (The TypeScript >>> 1 is an unsigned right-shift by one bit — a fast, overflow-safe integer halving, the JS idiom for the floor midpoint.)

Searching the answer space

Here is the leap that turns binary search into an interview superpower. There is no sorted array in sight — but there is a range of possible answers and a monotonic yes/no test, and that's all bisection ever needed. The recipe: (1) frame the unknown as "smallest k for which a condition holds," (2) confirm the condition is monotonic (F…F T…T), (3) find a valid [lo, hi] range, (4) run first-true bisection where f(k) is "is k good enough?"

Worked example — ship packages in D days. You have package weights w = [3, 2, 2, 4, 1, 4] loaded onto a conveyor in order, and D = 3 days. Each day a ship carries a contiguous run of packages whose total can't exceed the ship's capacity C. Find the smallest capacity C that still finishes within D days.

• The answer space is the candidate capacities. The smallest workable C is max(w) = 4 (a day must fit its heaviest single package). The largest you'd ever need is sum(w) = 16 (ship everything in one day). So lo = 4, hi = 16.
• The predicate f(C) = "can we ship within D days using capacity C?" Compute it greedily: walk the weights, keep adding to today's load; when the next package would overflow C, start a new day. Count the days; return days <= D.
• Monotonicity holds: a bigger ship can do anything a smaller one can, so once f(C) is true it stays true for every larger C. That F…F T…T shape is exactly the flip point first-true bisection finds.

def ship_within_days(w, D):
    def f(C):                      # can capacity C finish in <= D days?
        days, load = 1, 0
        for x in w:
            if load + x > C:        # today is full -> open a new day
                days += 1
                load = 0
            load += x
        return days <= D
    lo, hi = max(w), sum(w)     # answer range; f(hi) is guaranteed True
    while lo < hi:               # first-true bisection over capacities
        mid = lo + (hi - lo) // 2
        if f(mid): hi = mid          # mid works -> maybe smaller works too
        else:      lo = mid + 1     # mid too small -> need more capacity
    return lo                    # smallest capacity that ships in D days  (-> 6 here)

The cost is O(n log(sum)): each predicate call is one linear pass (O(n)), and bisecting the capacity range costs O(log(sum - max)) calls. We never enumerated the answers — we halved a numeric range, asking one greedy question per step. That's "binary search on the answer" in full.

Recognition signals & pitfalls

Get the bounds exactly right — the classic place to off-by-one or infinite-loop. Write it and the runner will tell you (it kills runaway loops after 2s):