Day 33 · Halving the phone book

Binary Search & Variants

You will be able to

Write a bug-free classic binary search and defend every boundary choice
Explain invariant thinking as the cure for off-by-one errors
Implement first/last-occurrence (boundary) search
Recognize and solve "search on the answer space" problems
Use the bisect module for insertion points and range counting

Today's ~120 minutes

Spaced-rep warm-up: due cards (sorting, graphs, heaps)	10 min
ELI5 + tech read; step the visualizer and predict each probe	18 min
Guided: classic + boundaries, rotated + Koko	42 min
Practice: ship packages within D days	20 min
Project: toolkit + config auto-tuner	20 min
Quiz + flashcards	10 min

Builds on: Day 22 — Big O & complexity · Day 32 — Sorting · Day 29 — Binary trees & BSTs

The analogy

🧸 ELI5⚙ Tech

Finding "Nakamura" in a paper phone book, nobody starts at page 1. You split the book in the middle — "Miller" — too early, so Nakamura lives strictly in the right half, and you have eliminated half the book with one glance. Split the survivor, glance, discard half again. A 1,000-page book takes ten glances; a million pages, twenty. That is binary search: each look kills half the possibilities, which is Day 22's O(log n) signature.

The famous catch: binary search is easy to describe and notoriously easy to implement wrong — the first published version took years to get right in print. The cure is not cleverness but a *promise you refuse to break*: "the answer, if it exists, is always inside [lo, hi]." Every line of the loop must keep that promise true — that is an invariant, and checking your code against it beats staring at ±1s.

The bigger unlock: the "phone book" does not have to be a list. Any question shaped "no no no no YES yes yes" — falses then trues — can be halved. "Can I ship all packages with capacity C?" is monotonic in C, so you binary-search over *candidate answers*, using a checker function as your glance.

Why this matters on the job

O(log n) is the difference between touching 20 items and 20 million, which is why binary search underlies everything fast: Day 38's B-tree index descent is binary search adapted for disk pages, git bisect halves your commit history to find the breaking change (a debugging move you will use for real), and capacity tuning ("lowest rate limit that stops 429s", "largest chunk size that stays under the token budget" on Day 114) is search-on-answer thinking. In interviews, boundary variants ("first bad version", "search rotated array", "Koko eating bananas") are prized precisely because they punish sloppy invariants — the discipline is the skill being tested.

Watch it happen

Watch the range halve — find 23 in 9 sorted values

step 1 / 6

A sorted array. Target: 23. Binary search only works because order lets us discard half at every step.

🎯 Predict modespeed1×

Guided practice

guided 1

The classic + the boundary template

20 min

Create binary_search_lab.py. Write binary_search(a, target) from the invariant, narrating each branch: "mid is too small, so the answer lives in [mid+1, hi]".
Fuzz it — the starter compares your function against list.index on 1,000 random sorted lists including empties, singletons, missing targets, and duplicates. A subtle off-by-one WILL be caught here; fix by re-checking the invariant, not by trial-and-error ±1.
Classic 1 — first and last occurrence. Implement first_pos and last_pos with the record-and-continue boundary template. Test on [5, 7, 7, 7, 8] for target 7 → (1, 3), and on a missing target → (-1, -1).
Cross-check with bisect_left/bisect_right and confirm: count of 7s == bisect_right - bisect_left. Two lines, no loop — the stdlib version of what you just wrote.

🐍 python — editable, runs in your browser

import random
from bisect import bisect_left, bisect_right

def binary_search(a, target):
    lo, hi = 0, len(a) - 1
    while lo <= hi:                     # invariant: answer (if any) in [lo, hi]
        mid = (lo + hi) // 2
        if a[mid] == target:
            return mid
        if a[mid] < target:
            lo = mid + 1                # mid ruled out -> exclude it
        else:
            hi = mid - 1
    return -1

def first_pos(a, target):
    lo, hi, ans = 0, len(a) - 1, -1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == target:
            ans = mid                   # record, then keep pushing LEFT
            hi = mid - 1
        elif a[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return ans

# fuzzer: your search vs the naive truth
for trial in range(1000):
    a = sorted(random.sample(range(50), random.randint(0, 20)))
    t = random.randint(0, 50)
    got = binary_search(a, t)
    if t in a:
        assert a[got] == t, (a, t, got)
    else:
        assert got == -1, (a, t, got)
print("fuzz passed")

a = [5, 7, 7, 7, 8]
print(first_pos(a, 7), bisect_left(a, 7))          # 1 1
print(bisect_right(a, 7) - bisect_left(a, 7))      # 3 sevens

Ctrl/⌘+Enter runs · Tab indents · numpy/pandas/sklearn auto-load on import (torch and network calls need a local run)

guided 2

Rotated arrays + Koko eats bananas, think-aloud

22 min

Classic 2 — minimum of a rotated sorted array ([4,5,6,7,0,1,2]). Think aloud: "Sorted-then-rotated means TWO sorted runs; the minimum is the seam. Compare a[mid] with a[hi]: if a[mid] > a[hi], the seam is strictly right of mid; else it is at mid or left." Implement find_min_rotated and test rotations 0..n-1 of range(8) exhaustively in a loop — the not-rotated-at-all case is the one that catches people.
Classic 3 — Koko eating bananas (search on answer). Koko has piles of bananas and h hours; eating speed k means each pile takes ceil(pile/k) hours. Find the MINIMUM k that finishes in time. Think aloud: "I cannot binary search the piles — but feasibility is monotonic in k: too slow fails, fast enough always works. So the answer space [1, max(pile)] is my phone book and feasible() is my glance."
Implement with the boundary template over the answer space. Test piles=[3,6,7,11], h=8 → 4.
State the complexity: O(n log max_pile) — and generalize aloud: "monotonic feasibility + numeric answer = binary search the answer."

🐍 python — editable, runs in your browser

def find_min_rotated(a):
    lo, hi = 0, len(a) - 1
    while lo < hi:                       # invariant: min is in [lo, hi]
        mid = (lo + hi) // 2
        if a[mid] > a[hi]:               # seam strictly right of mid
            lo = mid + 1
        else:                            # a[mid] could BE the min: keep it
            hi = mid
    return a[lo]

for r in range(8):                       # every rotation of 0..7
    a = list(range(8))[r:] + list(range(8))[:r]
    assert find_min_rotated(a) == 0, a
print("rotations passed")

def min_eating_speed(piles, h):
    def feasible(k):                     # can Koko finish at speed k?
        return sum((p + k - 1) // k for p in piles) <= h

lo, hi, ans = 1, max(piles), max(piles)
    while lo <= hi:
        mid = (lo + hi) // 2
        if feasible(mid):
            ans = mid                    # record, try slower (smaller k)
            hi = mid - 1
        else:
            lo = mid + 1
    return ans

print(min_eating_speed([3, 6, 7, 11], 8))    # 4
print(min_eating_speed([30, 11, 23, 4, 20], 5))  # 30

Ctrl/⌘+Enter runs · Tab indents · numpy/pandas/sklearn auto-load on import (torch and network calls need a local run)

On your own

Ship packages within D days

20 min

A conveyor belt must ship packages (given weights, in order — no reordering) within D days. Each day you load consecutive packages up to a capacity limit. Find the minimum capacity that ships everything in D days.

Constraints: O(n log(sum of weights)). Identify lo (think: what capacity is forced by the heaviest single package?) and hi before coding. Test: weights 1..10, D=5 → 15.

Hints: this is Koko in a shipping costume — feasible(capacity) greedily fills days and checks days_used <= D. lo = max(weights) (a package cannot be split), hi = sum(weights) (one giant day).

Ship before you stop

Binary search toolkit + a config auto-tuner

In dsa/binsearch.py, collect today's five functions (classic, first/last, rotated min, Koko, ship-capacity) with the fuzz tests. Then the transfer task, autotune.py: the starter's simulate(batch_size) function (provided stub — it mimics a service that gets faster with bigger batches until it starts failing past a hidden memory threshold) must be tuned. Binary-search the largest batch size whose simulate() call reports success, in at most 12 probes for a 1..4096 range. Print each probe — the log should read like a bisection. Commit; write one docstring line connecting this to git bisect.

Rubric — check what you completed (0/5)

Classic search survives the 1,000-case fuzzer including empties and duplicatesRotated-min passes the exhaustive all-rotations testKoko and ship-capacity share a visibly identical boundary templateAuto-tuner finds the hidden threshold in ≤ 12 probes with a printed probe logCommitted with tests green and the git-bisect connection noted

Common mistakes & misconceptions

Fixing off-by-ones by sprinkling ±1 until tests pass. State the invariant ("answer is in [lo, hi]") and derive every update from it — that is the actual skill.
Writing lo = mid (not mid + 1) after ruling mid out — on a two-element range mid == lo and the loop never shrinks: infinite loop.
Returning ANY match when the problem needs the FIRST. Duplicates demand the boundary template (record and continue), not the classic three-way search.
Missing that binary search requires sorted data — or a monotonic predicate. On unsorted data it returns garbage without erroring.
Not recognizing search-on-answer: if the answer is numeric and feasibility is monotonic ("if k works, k+1 works"), the answer space is the array.
Confusing bisect_left and bisect_right: left = first insertion point (first occurrence); right = past the last. Their difference counts occurrences.

Knowledge check

Q1. Your binary search loops forever on a = [3, 8] searching for 8. The most likely bug?

Q2. Which problem is NOT solvable by binary search?

Q3. In sorted a with duplicates, what does bisect_right(a, x) - bisect_left(a, x) compute?

Go deeper — curated resources

docsbisect — official Python docs ↗15 min toolVisuAlgo — BST/search visualizations (watch the halving) ↗10 min bookOpenDSA — Search chapter ↗20 min courseNeetCode Roadmap — Binary Search section ↗15 min

If you have a third hour

git bisect on a real repo — Intentionally break a test in your practice repo several commits back, then use git bisect run pytest to find the culprit automatically. Binary search over history — 4 probes for 16 commits.

Done means

Classic search passes the 1,000-case fuzzer untouched
First/last occurrence matches bisect_left/bisect_right on all tests
Koko and ship-capacity solved with the search-on-answer template
Auto-tuner converges in ≤ 12 probes; toolkit committed
Quiz ≥ 2/3

How this connects

← Back: The halving is Day 22's O(log n) row made mechanical, Day 32's sorting is the precondition that makes it legal, and Day 29's BST search was this same walk through pointers instead of indexes.

Forward →: Day 38's B-tree index descent is binary search restructured for disk. Day 34 meets problems where halving fails and memoization takes over. The search-on-answer pattern returns for capacity planning on Day 160, and git bisect is this algorithm applied to your commit history.

Unlocks: D35 Week 5 Checkpoint: Interview Drill I · D38 Database Internals