ZERO / HERO
Halving the phone book

O(log n) — Logarithmic

The analogy

Tear the phone book in half and throw away the half that cannot contain your name. Do it again. A million names takes about twenty tears. Doubling the book adds a single extra step — this is the best kind of scaling there is.

Visualizer

Tearing the phone book

step 1 / 10
Adeyemi
0
Bhatt
1
Chen
2
Duarte
3
Eriksson
4
Fontaine
5
Gupta
6
Haruki
7
Ivanov
8
Jandali
9
Kovács
10
Larsson
11
Mbeki
12
Nakamura
13
Okonkwo
14
Pham
15

16 pages. Finding "Mbeki" by reading page 1, then page 2, then page 3 would be madness.16 pages, looking for Mbeki

def find_page(pages, name):
    lo, hi = 0, len(pages) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if pages[mid] == name:
            return mid
        if pages[mid] < name:
            lo = mid + 1
        else:
            hi = mid - 1

# 1_000_000 names -> about 20 tears
Check yourself

Doubling the input for an O(log n) algorithm adds…