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

In Chapter 42 we made a list sorted, and paid O(n log n) for it. Now we spend that order. A sorted array unlocks a search so fast it feels like cheating: two markers, one probe, and half the list gone on every pass. That's binary search, the loop that trace T23 stepped through line by line. Here's the plan. First we pin down the one sentence that makes the loop correct — the invariant — and see why just three lines have tripped up some of the best programmers alive. Then comes the reveal almost no beginner is taught: you can binary-search things that aren't arrays at all. Finally we reach quickselect, which pulls the median out of a billion numbers without ever sorting them. All the 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, and you'll 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 keeps in memory. Just three integers: lo, hi, and a scratch value mid. That's the entire state. It never copies the list, no matter how big the list gets (O(1) extra space, exactly as T23's memory panel showed). So what makes this tiny loop correct? Not the code itself, but a single sentence. It 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 defends it. You probe the midpoint. If arr[mid] is smaller than the target, then every slot from lo up to and including mid is also too small, because the list is sorted. The target cannot be in any of them. 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 the same thing on the other side. The window can only shrink, and it never sheds the answer.

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 let's derive the speed instead of quoting it. Each pass replaces the window with one of its halves: n becomes n/2, then n/4, then n/8, and so on. How many halvings does it take until only one slot is left? That is just the number of times you can divide n by two before you reach 1, which is 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, which forces 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 and let it land: a billion sorted items, found in 30 comparisons. Multiply the data by a thousand, and the work grows by only ten. That is what living on the O(log n) curve buys you (green's frugal cousin from the volume's opening chart). The search race in the Algorithms Lab lets you watch linear's counter blow past it live.

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, famously reported that when he asked roomfuls of professional programmers to write a bug-free binary search, the great majority failed. The result gets repeated because it keeps coming true. The loop is tiny, but the bugs hide in four tiny decisions: < versus <=, and mid versus mid ± 1 on each side. Get 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

Take Bug A line by line: search for 55. The window narrows to lo=3, hi=4, so mid = (3+4)//2 = 3, and arr[3]=44 < 55. That sets lo = mid = 3, which leaves it unchanged. The next pass has the same lo, the same hi, and the 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," but the code kept it.

Bug B is subtler and nastier, because 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 gets 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. No crash, no red. Just the wrong answer, quietly, every so often. That is why binary search is legendary: the bugs don't announce themselves.

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 this 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.

Here is the move on a problem with no array to search. A ship loads packages off a conveyor in fixed order, and 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, since more capacity can only mean the same number of days or fewer. So "can we finish in D days with capacity C?" is monotonic in C: false, false, false, then true forever. We don't search the packages; we binary-search the capacity.

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

Line by line: days_needed walks the packages once and counts the days a given capacity forces. That's the O(n) feasibility check. feasible wraps it into the monotonic question. The search bounds come from the problem itself. Capacity can't be less than the heaviest single package, since it must at least fit, and it never needs to exceed the total, since that ships everything in one day. Then comes the familiar loop, but running over capacities instead of 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. The 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 bounds around it. Integer square root is the same idea in miniature. "Is mid² ≤ n?" is monotonic in mid, so a hand-written isqrt(n) is a binary search on the answer, and it agrees with the standard library's math.isqrt right up to isqrt(10**18) = 1000000000.

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 the list 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) work to answer an O(n) question. Quickselect pays only for what you need.

It borrows quicksort's partition step (detailed in trace T28): pick a pivot, then rearrange so everything smaller sits to its left and everything larger sits to its right. After one partition the pivot sits in its final sorted position, say index p, for free. Here is the key difference from quicksort. Quicksort recurses into both sides. 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 and 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 let's count the work instead of quoting it. The first partition scans all n elements. Then you keep one side, on average about half, so the next partition scans about n/2, the next about n/4, and so on. Add them up: n + n/2 + n/4 + … = 2n. This is a geometric series that converges, so the total work is proportional to n, which is O(n) average. Sorting's recursion keeps both halves and never gets to collapse that series. Quickselect's "recurse into one side" is exactly what drops 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 about 3.3 regardless of n, which is the signature of linear growth. (The constant sits above the ideal 2 because a random pivot isn't a perfect median, but it's still a constant.) For n = 16,000, that's about 53,000 comparisons versus roughly 223,000 for a full comparison sort. You got the median with a quarter of the work, and you never produced a sorted list you didn't want.

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 already 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 say "good" or "bad," and half the timeline is eliminated. That's the same monotonic structure as the ship: once broken, it stays broken. A thousand commits, found in about ten checkouts. Debugging a long function by commenting out the first half to see if the bug survives? Same move. Bisection is the everyday face of binary search, and naming it makes you faster at it.

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

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

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. →