43Searching & selection — binary search is bigger than you think

In Chapter 42 we made a list sorted, and we paid O(n log n) for the privilege. Here we cash that order in. A sorted array unlocks a search so fast it feels like cheating. Two markers, one probe, and half the list gone every pass — that's binary search, the loop that trace T23 steps line by line. Here's the plan. First we nail the one sentence that makes the loop correct, the invariant, and see why three lines have bitten the best programmers alive. Then comes the reveal almost nobody learns as a beginner: you can binary-search things that aren't arrays at all. Finally we meet quickselect, which pulls the median out of a billion numbers without ever sorting them. The whole way through we keep asking the one question that turns a coder into an engineer — what is the least work this problem actually demands? By the end you'll spot binary search hiding in problems that look nothing like search. You'll also refuse to sort when all you needed was one position.

01The invariant — the promise the loop never breaks

Let's start with what binary search actually holds in memory. Three integers: lo, hi, and a scratch mid. That's the entire state, with no copies of the list, no matter how many millions of items sit inside it. That is O(1) extra space, exactly what T23's memory panel showed while you stepped it. So what makes this tiny loop correct, given that the code is only a few lines? Not the code itself — the answer is a single sentence, one that is true before the loop starts, stays true after every pass, and is still true the instant it stops. That sentence is the loop invariant:

If the target is in the list at all, it is somewhere in the window [lo, hi].

Watch how each step of the loop defends that sentence. You probe the midpoint, and suppose arr[mid] comes back smaller than the target. Because the list is sorted, every slot from lo up to and including mid must also be too small to match. The target cannot be sitting in any of those slots, so you move lo = mid + 1. You just threw away half the window, and the promise still holds, because you only discarded slots you proved couldn't hold the target. The mirror move, hi = mid - 1, does exactly the same thing on the other side. The window can only shrink, and it never sheds the answer.

There are two more things the invariant hands you, both for free. First, termination: every pass moves lo up or hi down by at least one, so the window loses at least one slot per pass. A window that only shrinks must eventually reach size zero, which means the loop cannot run forever. Second, the exit is just as principled as the steps. If lo ever crosses past hi, the window [lo, hi] is empty. Now reread the invariant: if the target were in the list, it would be inside that window. The window holds nothing, so the target is provably absent, and reporting "not found" is not a guess. That is what an invariant buys you: the loop's answer comes with a proof attached.

def bsearch(arr, target):
    lo, hi = 0, len(arr) - 1          # invariant: answer, if present, is in [lo, hi]
    while lo <= hi:                    # window still holds at least one slot
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid                # found it
        elif arr[mid] < target:
            lo = mid + 1              # left half proven too small — discard it
        else:
            hi = mid - 1              # right half proven too big — discard it
    return -1                         # window emptied — the target was never here

Now derive the speed, don't quote it. Each pass replaces the window with one of its halves: n becomes n/2, then n/4, then n/8… How many halvings until only one slot is left? That is the number of times you can divide n by two before hitting 1 — the definition of log₂ n. So the loop runs at most about log₂ n times. Counting the real worst-case probes (a target just past the end, forcing the deepest possible search) confirms it exactly:

n=            1  probes(worst)=  1   ceil(log2(n+1))=1
n=           10  probes(worst)=  4   ceil(log2(n+1))=4
n=        1,000  probes(worst)= 10   ceil(log2(n+1))=10
n=    1,000,000  probes(worst)= 20   ceil(log2(n+1))=20
n=1,000,000,000  probes(worst)= 30   ceil(log2(n+1))=30

Read the last line of that output and let it land: a billion sorted items, found in 30 comparisons. Multiply the data by a thousand and the work grows by ten. That is what living on the O(log n) curve buys you, green's frugal cousin from the volume's opening chart. Open the search race in the Algorithms Lab and watch linear's counter blow past it live.

Where does that 30 come from? Run the halving by hand once, so the logarithm is a thing you've touched rather than a formula you trust. Start with 1,024 slots: one probe leaves 512, then 256, 128, 64, 32, 16, 8, 4, 2, 1. Count the steps on your fingers and you get exactly 10 halvings, and sure enough 2**10 = 1024. Now stretch the same ladder up to a billion. Since 2**30 = 1,073,741,824, a list of a billion items collapses to a single slot in about 30 probes. The logarithm is not magic — it is counting halvings, and you just counted them.

Three lines, one promise. So why did one of the field's most famous essays claim that almost no one writes them correctly? →

02Why binary search is the bug that ate the industry

Jon Bentley, in Programming Pearls, reported a famous experiment on this exact loop. He asked roomfuls of professional programmers to write a bug-free binary search, and the great majority failed. The result gets repeated so often because it keeps coming true. The loop is tiny, yet the bugs hide in four tiny decisions: < versus <=, and mid versus mid ± 1 on each side. Get any one of them wrong and the invariant tears. Here are two classic tears, run for real:

arr = [11, 22, 33, 44, 55]

# BUG A — write  lo = mid  instead of  lo = mid + 1
def bug_infinite(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if   arr[mid] == target: return mid
        elif arr[mid] <  target: lo = mid       # <- forgets the +1
        else:                    hi = mid - 1
    return -1

# BUG B — write  while lo < hi  instead of  lo <= hi
def bug_misses(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo < hi:                               # <- a 1-slot window never gets checked
        mid = (lo + hi) // 2
        if   arr[mid] == target: return mid
        elif arr[mid] <  target: lo = mid + 1
        else:                    hi = mid - 1
    return -1

Line by line on Bug A: search for 55. The window narrows to lo=3, hi=4; mid = (3+4)//2 = 3; arr[3]=44 < 55, so lo = mid = 3 — unchanged. Next pass: same lo, same hi, same mid, forever. Because mid rounds down, dropping the +1 lets lo get stuck on a slot it already rejected. The invariant said "discard mid"; the code kept it.

Bug B is subtler and nastier — it returns a confident wrong answer. Using lo < hi, the loop quits the instant the window shrinks to a single slot (lo == hi), without checking that slot. So any element that ends up alone in the final window is reported as absent. Here is what the two bugs actually print:

correct(arr, 55)      -> 4
bug_infinite(arr, 55) -> INFINITE LOOP (hit safety cap at 1000 iterations)

correct(arr, 55)      -> 4
bug_misses(arr, 55)   -> -1
bug_misses fails to find: [22, 55]

Bug B doesn't fail on 55 alone — it silently loses 22 too, and on a bigger array it loses a different scattered handful. There is no crash, no red text, no traceback to point at. The search just occasionally, quietly, hands back the wrong answer, and nothing warns you it happened. That is why binary search is legendary: the bugs don't announce themselves.

This isn't just a classroom hazard, and here is the receipt. In 2006, Joshua Bloch, the engineer behind Java's collections, published a now-famous post about this exact loop. The binary search in java.util.Arrays was broken, and the bug had sat in the JDK for roughly nine years before anyone caught it. The version printed in Programming Pearls — the very book that set the challenge above — carried the same flaw. Millions of programs called that method in production, and the failure waited patiently for arrays large enough to trigger it. What was the flaw? Not any of the four decisions we just walked through, and that is exactly why it deserves its own paragraph.

lo, hi = 1_500_000_000, 1_700_000_000   # both valid indices
true lo+hi            = 3200000000
as signed 32-bit int  = -1094967296     <- overflowed NEGATIVE
bad mid = (lo+hi)//2  = -547483648      <- negative index -> crash
safe mid = lo+(hi-lo)//2 = 1600000000   <- never overflows

You now own the loop cold. Time for the part they don't tell beginners: the array is optional. →

03Binary-search the answer, not the array

Strip binary search down to what it truly needs. Not a list. Not even numbers-in-a-row. It needs exactly one thing: a yes/no question that is monotonic — once the answer flips to "yes," it stays "yes" for everything past that point. A sorted array is just one place that shows up ("is arr[i] ≥ target?" flips from no to yes exactly once). But any monotonic yes/no gives you the same superpower: binary-search the space of possible answers.

You already know this move from a children's game. Think of a number between 1 and 100, and I'll guess it, with you answering only "higher" or "lower." My question "is your number bigger than 50?" is a monotonic yes/no. Below your secret number every probe reads low, above it every probe reads high, so the answer flips exactly once. So I guess midpoints, and each answer kills half the candidates. Seven questions settle it every time, because 2**7 = 128 is enough to cover all 100 possibilities. Notice what was never required to make that work: no array, no list, no data structure at all. Just a question whose answer flips once and stays flipped.

Here is the move on a problem with no array to search. A ship loads packages (in fixed order) off a conveyor; with a weight capacity C it takes some number of days. You must deliver everything within D days. What is the minimum capacity that still makes the deadline? Brute force would try every capacity from small to large. But notice the structure: a bigger ship is never worse — more capacity can only mean the same or fewer days. So "can we finish in D days with capacity C?" is monotonic in C: false, false, false, then true forever. We don't search packages; we binary-search the capacity.

Make the day-count concrete with three packages before reading any code. Say the weights are 5, 4, 6 and the ship's capacity is 9. Day one loads 5 and then 4, because 5 + 4 = 9 fits exactly, and day two carries the 6 alone — that's 2 days. Now shrink the capacity to 8 and rerun it. The 4 no longer fits beside the 5, so the loads become 5, then 4, then 6: 3 days. One unit of capacity gone, and the schedule got worse, never better. That is the monotone structure, touched with your own hands.

weights = [1,2,3,4,5,6,7,8,9,10];  D = 5

def days_needed(cap):                 # simulate one candidate capacity — O(n)
    days, load = 1, 0
    for w in weights:
        if load + w > cap:            # this package won't fit today
            days += 1; load = 0       # start a new day
        load += w
    return days

def feasible(cap): return days_needed(cap) <= D    # the monotonic yes/no

lo, hi = max(weights), sum(weights)   # smallest sane cap … ship-it-all-in-a-day cap
while lo < hi:
    mid = (lo + hi) // 2
    if feasible(mid): hi = mid        # mid works — the answer is mid or smaller
    else:             lo = mid + 1    # mid too small — need strictly more
answer = lo

Read it line by line. days_needed walks the packages once and counts how many days a given capacity forces, and that's the O(n) feasibility check. feasible then wraps that day-count into the monotonic yes/no question from the last section. The search bounds come straight from the problem itself, and both are worth a second of thought. Capacity can't be less than the heaviest single package, because that one package must at least fit on board. It never needs to exceed the total weight either, because a ship that big carries everything in one day. Then comes the familiar loop, except it now runs over capacities, not indices — watch it run:

search range [10, 55]  (46 possible capacities)
minimum feasible capacity = 15   (days it needs: 5)
feasibility checks performed = 5           <- vs up to 46 for a linear sweep

  window [10,55]  try C=32  -> 2 days  feasible=True
  window [10,32]  try C=21  -> 3 days  feasible=True
  window [10,21]  try C=15  -> 5 days  feasible=True
  window [10,15]  try C=12  -> 6 days  feasible=False
  window [13,15]  try C=14  -> 6 days  feasible=False

Five checks instead of forty-six, and it scales the same beautiful way: log₂(range) feasibility checks, no matter how wide the range gets. The total cost is O(n · log(range)), so the range can be astronomically large and you'd barely notice. The whole trick was spotting the monotonic yes/no and building honest bounds around it. Integer square root is the same idea in miniature. The question "is mid² ≤ n?" is monotonic in mid, so a hand-written isqrt(n) is just a binary search on the answer. It agrees with the standard library's math.isqrt right up to isqrt(10**18) = 1000000000.

you type
$ python bisect_idiom.py

import math
from bisect import bisect_left, bisect_right, insort

# ---------- 1. the two bisects: where does 44 belong? ----------
a = [11, 22, 33, 44, 44, 44, 55]
print(bisect_left(a, 44), bisect_right(a, 44))
print(bisect_left(a, 40), bisect_right(a, 40))

# ---------- 2. the membership idiom (bisect has no "found" flag) ----------
def contains(seq, x):
    i = bisect_left(seq, x)
    return i < len(seq) and seq[i] == x
print(contains(a, 44), contains(a, 40))

# ---------- 3. insort keeps a list sorted as it grows ----------
scores = [10, 30, 50]
insort(scores, 40)
insort(scores, 5)
print(scores)

# ---------- 4. key= (3.10+): the list is keyed, the target is a KEY ----------
rows = [("ada", 31), ("bex", 44), ("cy", 55)]
print(bisect_left(rows, 44, key=lambda r: r[1]))

# ---------- 5. the bucket lookup: grades from cut-offs ----------
cuts, grades = [60, 70, 80, 90], "FDCBA"
print([grades[bisect_right(cuts, m)] for m in (55, 60, 79, 90, 100)])

# ---------- 6. binary-search an ANSWER — there is no list ----------
def first_true(lo, hi, pred):
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if pred(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

n = 10**18
print(first_true(0, n, lambda m: m * m > n) - 1, math.isqrt(n))

# ---------- 7. two traps, side by side ----------
print(first_true(0, 10**9, lambda m: m * m > n) - 1)   # hi too small
u = [55, 11, 44, 22, 33]
print(bisect_left(u, 22), contains(u, 22))             # list not sorted

you see
3 6
3 3
True False
[5, 10, 30, 40, 50]
1
['F', 'D', 'C', 'A', 'A']
1000000000 1000000000
999999999
2 False

Searching finds a value. What if you want a value by its rank — the median, the 90th percentile — out of a billion unsorted numbers? →

04Quickselect — the median without sorting

The obvious way to get the median is to sort and grab the middle. But sorting does far more work than you asked for: it puts every element in order when you only wanted one position. That's O(n log n) to answer an O(n) question. Quickselect pays only for what you need.

Let's pin down the word rank before it starts doing work. The rank-k element is the value that would sit at index k if the list were sorted. No sorting has to actually happen for that value to exist. Take [7, 1, 9, 4, 3], whose sorted order is [1, 3, 4, 7, 9]. Rank 0 is 1, rank 2 is 4, and rank 4 is 9. The median of five items is just the rank-2 element, the one with two values below it and two above. A p95 latency is the same species: the element at rank 0.95 · n, give or take rounding. Every one of these is a single position, which is exactly the question quickselect answers.

Quickselect borrows quicksort's partition step, the one trace T28 details. Pick a pivot, then rearrange the array so everything smaller sits to its left and everything larger sits to its right. After that one pass the pivot lands in its final sorted position (call it index p), and you got that placement for free. Now comes the key difference from quicksort. Quicksort recurses into both sides of the pivot. Quickselect looks at p, compares it to the rank k you want, and recurses into only the side that contains k. The other half is thrown away, unsorted, unexamined.

def quickselect(a, k):                 # k-th smallest, 0-indexed
    a = a[:]                           # copy; partition rearranges in place
    lo, hi = 0, len(a) - 1
    while lo < hi:
        p = partition(a, lo, hi)       # pivot lands at its final index p
        if   p == k: break             # the pivot IS the k-th smallest — done
        elif p <  k: lo = p + 1         # k is to the RIGHT — discard the left
        else:        hi = p - 1        # k is to the LEFT  — discard the right
    return a[k]

Now count the work rather than quoting it. The first partition scans all n elements. Then you keep one side, on average about half, so the next partition scans ~n/2, the one after ~n/4, and so on down. Sum the whole thing: n + n/2 + n/4 + … = 2n. That is a geometric series that converges, so the total work stays proportional to n — in other words, O(n) average. Sorting's recursion keeps both halves alive and never gets to drop that series. Quickselect's "recurse one side" is exactly the move that collapses the log n factor. Measured on random data, the comparisons stay a flat constant-times-n no matter how big n gets:

median of [200, 90, 150, 60, 247, 245, 33]
  quickselect -> 150   (statistics.median -> 150)   using only 14 comparisons
  the list was never sorted

 n      : avg quickselect comparisons (median, 100 runs) : ratio to n
   1000 :         3322                                    : 3.32 x n
   2000 :         6631                                    : 3.32 x n
   8000 :        26319                                    : 3.29 x n
  16000 :        53182                                    : 3.32 x n

The ratio holds at ~3.3 regardless of n, and a ratio that refuses to move is the signature of linear growth. The constant sits above the ideal 2 because a random pivot isn't a perfect median. But it is still a constant, and constant is the word that matters. For n = 16,000, that's about 53,000 comparisons versus roughly 223,000 for a full comparison sort. In other words, you got the median with a quarter of the work, and you never produced a sorted list you didn't want.

Before we leave the arithmetic, check that series on a number small enough to trust. Take n = 16: the scans cost 16 + 8 + 4 + 2 + 1 = 31, and 31 sits safely under 2 × 16 = 32. The pattern holds at any size, because each term is half of the one before it. Doubling the input adds one bigger term at the front, yet the total stubbornly stays under twice the first scan. That is what a convergent series means in cash terms: infinitely many terms, a finite bill. A sort never gets this gift, because it keeps both halves at every level and pays n per level for log₂ n levels.

Fast, correct, frugal. Now — where does all this actually run, and what's the mental move to carry out of the chapter? →

05The move to steal: turn problems into monotone questions

You have probably used binary search this week without noticing. When you run git bisect to find the commit that introduced a bug, git binary-searches your history. It checks out the middle commit, you answer "good" or "bad," and half the timeline is eliminated on the spot. The structure is the same monotonic flip as the ship: once broken, the history stays broken. So a thousand commits are found in about ten checkouts — the same halving ladder you counted earlier. Debugging a long function by commenting out the first half to see if the bug survives is the same move. Bisection is the everyday face of binary search, and naming the move makes you faster at it.

Selection shows up just as widely once you know its name. Every time a dashboard shows you a p95 latency or a median income, something computed a rank statistic. At scale that something is not sorting billions of rows. It is quickselect, or one of its streaming cousins like the approximate-quantile sketch called t-digest. Database query planners lean on selectivity estimates to guess how many rows a filter will keep. And "give me the top 100 without ordering all ten million" is a call to argpartition, not sort.

That is the 1% reframe hiding in this chapter, so let me say it plainly. Beginners memorize a slogan: "binary search = find a number in a sorted array." Engineers see the deeper shape underneath it: binary search is a tool for any monotone predicate, and selection is a tool for any rank. Both come from the same discipline, refusing to do more work than the question demands. Don't sort when you need one position, and don't scan when the structure is monotone. Ask what you actually need, then pay exactly that.

import math
from bisect import bisect_left


def first_true(lo, hi, pred):
    """Smallest x in [lo, hi] with pred(x) True. One loop, any question."""
    assert lo <= hi
    while lo < hi:
        mid = lo + (hi - lo) // 2      # overflow-proof in every language
        if pred(mid):
            hi = mid                   # mid works -> answer is mid or left of it
        else:
            lo = mid + 1               # mid fails -> answer is strictly right
    return lo                          # lo == hi: the flip point


# ---- 1. a sorted list is just one monotone question -------------------
a = [11, 22, 33, 44, 44, 44, 55]
mine = first_true(0, len(a), lambda i: i == len(a) or a[i] >= 44)
print("bisect_left:", bisect_left(a, 44), "| first_true:", mine)

# ---- 2. isqrt: no list anywhere -------------------------------------
for n in (0, 1, 15, 16, 10**18):
    mine = first_true(0, n + 1, lambda m: m * m > n) - 1
    print(n, mine, math.isqrt(n), mine == math.isqrt(n))

# ---- 3. the real thing: how many machines finish the batch in time? ---
jobs = [7, 2, 5, 10, 8, 3, 9, 4]      # minutes per job
DEADLINE = 15                          # every machine must finish by then

def machines_needed(cap):
    """Greedy fill: one machine takes jobs in order until cap is reached."""
    used, load = 1, 0
    for j in jobs:
        if j > cap:
            return float("inf")        # this job alone busts the deadline
        if load + j > cap:
            used, load = used + 1, 0
        load += j
    return used

for k in (1, 2, 3, 4, 5):
    lo = first_true(1, sum(jobs), lambda cap: machines_needed(cap) <= k)
    print(f"  {k} machines -> finish in {lo} min "
          f"(check: {machines_needed(lo)} machines at cap {lo}, "
          f"{machines_needed(lo - 1)} at cap {lo - 1})")

best = first_true(1, sum(jobs), lambda cap: machines_needed(cap) <= 3)
print("3 machines finish in", best, "min ->",
      "OK" if best <= DEADLINE else "MISSES the 15-min deadline")

# ---- 3b. same driver, other axis: fewest machines that make the deadline ----
k = first_true(1, len(jobs), lambda k: machines_needed(DEADLINE) <= k)
print("fewest machines for a 15-min deadline:", k)

# ---- 4. the honest failure: feed it a NON-monotone question ----------
bumpy = [False, True, False, False, False, True]    # flips three times
print("non-monotone ->", first_true(0, 5, lambda i: bumpy[i]),
      "| the real first True is", bumpy.index(True))

# ---- 5. and the count that proves it never scans -----------------------
calls = 0
def slow(cap):
    global calls
    calls += 1
    return machines_needed(cap) <= 3
first_true(1, 10**9, slow)
print("range of 10**9 answers, feasibility checks:", calls)


# ---------- the actual run, python 3.12.7 ----------
#
# bisect_left: 3 | first_true: 3
# 0 0 0 True
# 1 1 1 True
# 15 3 3 True
# 16 4 4 True
# 1000000000000000000 1000000000 1000000000 True
#   1 machines -> finish in 48 min (check: 1 machines at cap 48, 2 at cap 47)
#   2 machines -> finish in 24 min (check: 2 machines at cap 24, 3 at cap 23)
#   3 machines -> finish in 18 min (check: 3 machines at cap 18, 4 at cap 17)
#   4 machines -> finish in 14 min (check: 4 machines at cap 14, 5 at cap 13)
#   5 machines -> finish in 13 min (check: 5 machines at cap 13, 6 at cap 12)
# 3 machines finish in 18 min -> MISSES the 15-min deadline
# fewest machines for a 15-min deadline: 4
# non-monotone -> 5 | the real first True is 1
# range of 10**9 answers, feasibility checks: 30
#
#
# ---------- reading it ----------
#
# 1. Three problems, one loop, and the loop never learned which one it was
#    solving. A sorted list, a square root, and a factory schedule are the
#    same question wearing three costumes: "where does False become True?"
#
# 2. Look at the check column in run 3. At cap 18 you need 3 machines; at
#    cap 17 you need 4. That IS the cliff, printed. first_true did not find
#    a minimum by comparing candidates -- it found the single place where
#    the answer changes, which is a much cheaper thing to look for.
#
# 3. Run 4 is the one to remember. The loop probed index 2 (False), jumped
#    right, probed 4 (False), jumped right again, and returned 5 -- while
#    the real first True sat at index 1, in the half it discarded on the
#    very first probe. No exception, no warning, no clue. Binary search
#    does not verify monotonicity; it ASSUMES it. If your predicate can
#    flip back, this loop is not a slow answer, it is a wrong one.
#
# 4. Run 5: a range of a billion candidate answers, settled in 30 checks,
#    because 2**30 is just over a billion. The range costs you almost
#    nothing. Whatever pred() costs is what you actually pay -- which is
#    why the engineering question is never "how wide is the space?" but
#    "how expensive is one honest yes/no?"

We've been searching straight lines and sorted ranges. But most real problems — maps, friend networks, web links, task dependencies — aren't lines at all; they're webs. The next chapter opens with the most general structure in all of computing: a graph, nothing but nodes and the edges between them — and the two ways to explore one that unlock GPS routing, PageRank, and six degrees of separation. →