Week 12 · Phase 4 · Choosing well

Searching: Linear vs Binary

Guess-the-number, the phone book trick, and why log n barely grows.

Big question: How do you find something in a million items with only 20 looks?binary search≈3 hours

By the end of this week you can

write linear search and binary search yourself;
trace a binary search by hand, following low, high and middle;
name the off-by-one bugs that make binary search loop forever or miss an item, and test against them;
explain why binary search needs sorted data, and what that costs;
show that log n grows so slowly it is almost constant in practice;
decide between scanning, sorting-then-searching, and building a set;
use Python's bisect module instead of writing your own.

12.1The game you already played

In week 1 you guessed a number between 1 and 100 by always choosing the middle of the remaining range, and it took at most seven guesses. That is binary search, and it is the second most useful algorithm a beginner can learn (the first is "put it in a dictionary").

Range size	Guessing one by one	Halving
100	up to 100	7
1 000	up to 1 000	10
1 000 000	up to 1 000 000	20
1 000 000 000	up to a billion	30
the world's population	8 billion	33

Thirty-three questions to find one person on Earth. That column is why O(log n) is treated as "practically free": between a thousand items and a billion, it grows from 10 to 30.

12.2Linear search, for reference

linear_search.py

def linear_search(data, target):
    """Return the position of target, or -1. Works on any list."""
    for i in range(len(data)):
        if data[i] == target:
            return i
    return -1

Worst case n comparisons: O(n). Its virtues are that it needs no preparation and works on unsorted data, which is exactly what you usually have.

12.3Binary search

The rule: look in the middle; if the target is smaller, throw away the right half; if larger, throw away the left half; repeat.

binary_search.py — data must be sorted

def binary_search(data, target):
    low = 0
    high = len(data) - 1
    steps = 0

    while low <= high:
        steps += 1
        middle = (low + high) // 2

        if data[middle] == target:
            return middle, steps
        elif target < data[middle]:
            high = middle - 1          # drop the right half
        else:
            low = middle + 1           # drop the left half

    return -1, steps

see the steps for yourself

data = list(range(1000000))          # already sorted

print(binary_search(data, 999999))   # (999999, 20)
print(binary_search(data, 0))        # (0, 20)
print(binary_search(data, -5))       # (-1, 20)

Twenty steps in a million-item list — for a hit at the far end, a hit at the near end, and a miss alike. Compare with linear search, which needs up to a million.

The two ways to get this wrong

Unsorted data. Binary search on unsorted data does not error — it silently returns wrong answers. That is worse than crashing.
Off-by-one. while low <= high, and middle ± 1 when narrowing. Get either wrong and you loop forever or miss the last item. Test with a 1-item list, a 2-item list, the first element, the last, and a missing value.

12.4Watch it run: a step-by-step trace

The code is short, but short code hides its behaviour. The cure is to trace it once by hand, writing down low, high and middle at every turn. Take this ten-item sorted list (indices along the top) and search for 23:

index	0	1	2	3	4	5	6	7	8	9
value	2	5	8	12	16	23	38	56	72	91

step	low	high	middle	data[middle]	decision
1	0	9	4	16	23 > 16 → search right, `low = 5`
2	5	9	7	56	23 < 56 → search left, `high = 6`
3	5	6	5	23	match → return (5, 3)

Three steps, and each one threw away roughly half of what was left: ten candidates, then five, then two. Now trace a miss — search for 40, which is not in the list:

step	low	high	middle	data[middle]	decision
1	0	9	4	16	40 > 16 → `low = 5`
2	5	9	7	56	40 < 56 → `high = 6`
3	5	6	5	23	40 > 23 → `low = 6`
4	6	6	6	38	40 > 38 → `low = 7`
5	7	6	—	—	`low > high` → return (−1, 4)

The loop ends the instant low overtakes high: the window has closed to nothing, so the value cannot be present. That crossing is the whole reason the condition is while low <= high and not < — with <, a one-element window (low == high) is never examined, and a value sitting there is missed.

Counting the halvings

Each step at most halves the window, so the number of steps is about how many times you can halve n before reaching one — which is log₂ n, rounded up. For n = 10 that is 4; for n = 1 000 000 it is 20. The steps counter the function returns is log₂ n made visible.

12.5The off-by-one minefield

Binary search is famous for being easy to describe and hard to get exactly right. Almost every bug is one of three kinds. Here is a version with the classic mistake planted in it — predict what it does before reading on:

buggy_binary_search.py — do not ship this

def buggy_search(data, target):
    low, high = 0, len(data) - 1
    while low <= high:
        middle = (low + high) // 2
        if data[middle] == target:
            return middle
        elif target < data[middle]:
            high = middle              # BUG: should be middle - 1
        else:
            low = middle + 1
    return -1

Run it on [10, 20] searching for 5. Step 1: low 0, high 1, middle 0, data[0] is 10, and 5 < 10, so high = middle = 0. Step 2: low 0, high 0, middle 0, still 5 < 10, so high = 0 again. Nothing has changed. It loops forever. The fix — high = middle - 1 — guarantees the window shrinks on every branch, so low and high must eventually cross.

Mistake	Symptom	The rule
`while low < high`	Misses a value sitting in a one-element window	Use `<=` so `low == high` is still checked
`high = middle` (no −1)	Infinite loop when the window will not shrink	Always move past the middle: `middle − 1` / `middle + 1`
Searching unsorted data	Wrong answer, no error	Sort first, or use a set — precondition, not optional

The defence is not cleverness, it is a fixed set of tests. Any binary search you write should be tried on: an empty list, a one-item list, a two-item list, the very first element, the very last element, and a value that is absent. If all six pass, the function is almost certainly correct.

A useful cousin returns not "is it here?" but "where would it go?" — the insertion point. This is what powers bisect in the next section, and it never needs the equality branch at all:

insertion_point.py

def insertion_point(data, target):
    """First index i such that everything left of i is < target."""
    low, high = 0, len(data)          # note: high starts at len, not len-1
    while low < high:
        middle = (low + high) // 2
        if data[middle] < target:
            low = middle + 1
        else:
            high = middle
    return low

data = [10, 20, 30, 40, 50]
print(insertion_point(data, 30))      # 2  — 30 belongs at index 2
print(insertion_point(data, 35))      # 3  — between 30 and 40
print(insertion_point(data, 99))      # 5  — past the end

2 3 5

Notice the deliberately different shape: high starts at len(data) and the loop is while low < high with high = middle (no −1). The two idioms are not interchangeable — each is internally consistent, and mixing pieces of one into the other is how the bugs above are born. Learn one of each and keep them separate.

12.6But sorting is not free

Binary search costs O(log n) — if the data is already sorted. Sorting costs O(n log n), which is more than a single linear scan. So the arithmetic depends entirely on how many searches you will do.

Situation	Best choice	Total cost
One search, unsorted data	Linear search	O(n) — sorting first would cost more
Many searches, data stays put	Sort once, then binary search	O(n log n) once + O(log n) each
Many searches, you only ask "is it there?"	Build a set	O(n) once + O(1) each
Data already sorted for other reasons	Binary search	O(log n) each
You need neighbours, ranges, "next larger"	Sorted list + `bisect`	O(log n) each — a set cannot do this

Notice row three: for plain membership, a set beats binary search. Binary search earns its place when you need order — the nearest value, everything between two dates, the next larger measurement. That is a question a hash table cannot answer at all.

The crossover is worth doing on the back of an envelope. Say sorting a list costs about n log₂ n and each linear scan costs n. Sorting-then-searching for q queries costs roughly n log₂ n + q log₂ n; scanning q times costs q n. For n = 1 000 000, log₂ n ≈ 20, so sorting pays for itself once q climbs past about 20 — after that the scan is throwing away the same million items over and over, while binary search never looks at more than twenty.

12.7Do not write it yourself

Python ships with a tested implementation. Use it in real work; write your own only to understand it, as you did above.

bisect

import bisect

data = [10, 20, 30, 40, 50]

i = bisect.bisect_left(data, 30)
print(i, data[i] == 30)          # 2 True  — found at position 2

print(bisect.bisect_left(data, 35))   # 3 — where 35 would go
bisect.insort(data, 35)               # insert and keep sorted
print(data)                           # [10, 20, 30, 35, 40, 50]

bisect_left is O(log n). insort finds the spot in O(log n) but still has to shift items, so the insertion itself is O(n) — the week 10 lesson has not gone away.

bisect_left vs bisect_right

When the value is already present, bisect_left returns the index of the first copy and bisect_right the index just after the last. Their difference, bisect_right(data, x) - bisect_left(data, x), is exactly how many copies of x the list holds — an O(log n) count, no scanning. You will use this in Task 4.

12.8The benchmark

three strategies, one job

import time, random, bisect

def bench(n, queries=1000):
    data = list(range(n))
    targets = [random.randrange(n) for _ in range(queries)]

    start = time.perf_counter()
    for t in targets:
        linear_search(data, t)
    t_lin = time.perf_counter() - start

    start = time.perf_counter()
    for t in targets:
        bisect.bisect_left(data, t)
    t_bin = time.perf_counter() - start

    lookup = set(data)
    start = time.perf_counter()
    for t in targets:
        t in lookup
    t_set = time.perf_counter() - start

    print(f"n={n:>8}  linear {t_lin:8.4f}s   binary {t_bin:7.5f}s   set {t_set:7.5f}s")

for n in [10000, 100000, 1000000]:
    bench(n)

n= 10000 linear 0.4120s binary 0.00081s set 0.00007s n= 100000 linear 4.1932s binary 0.00098s set 0.00007s n= 1000000 linear 42.0517s binary 0.00119s set 0.00007s

Three completely different behaviours in one table: linear multiplies by ten each row, binary creeps up by a fifth (that is log n at work), and the set does not move. Everything in this course is visible in those three columns.

12.9Try it yourself

Task 1 — count the halvings

Use the steps value returned by binary_search to fill a table for n = 1 000, 10 000, 100 000, 1 000 000, 10 000 000 (worst case: search for a missing value). What is the pattern?

Expected

About 10, 14, 17, 20, 24. Each ten-fold increase in data adds roughly three or four steps. That is what "logarithmic" feels like from the inside.

Task 2 — break it deliberately

Run binary_search on an unsorted list and find a value it fails to locate even though it is present. Then explain in two sentences why no error was raised.

Task 3 — the crossover with sorting included

For a list of 1 000 000 unsorted items, compare total time for q searches, q = 1, 10, 100, 1 000, 10 000, under three strategies: (a) linear each time, (b) sort once then binary, (c) build a set once then look up. At what q does each strategy win?

What you should find

For a single search, plain linear wins — the preparation costs more than the scan. The set overtakes very quickly (usually within a handful of queries) because building it is only one pass. Sorting pays off later than the set for pure membership, but it is the only one of the three that also answers range questions.

Task 4 — a question a set cannot answer

Given a sorted list of a million timestamps, use bisect to count how many fall between two given values, in O(log n). Then try to do the same with a set and describe why it degrades to O(n).

Solution

range count

import bisect
count = bisect.bisect_right(data, high) - bisect.bisect_left(data, low)

Two O(log n) lookups and a subtraction. A set has no notion of order, so the only option is to examine every element — O(n). This is the reason sorted structures still exist in a world with hash tables.

Task 5 — trace it on paper

By hand, trace binary_search([3, 7, 9, 14, 21, 28, 33, 40], 33), writing low, high and middle at each step. How many steps? Then trace a search for 10 (absent) the same way.

Answer

Finding 33 (indices 0–7): mid 3 → data[3]=14, 33>14, low=4; mid 5 → data[5]=28, 33>28, low=6; mid 6 → data[6]=33, match. 3 steps. Searching for 10: mid 3 → 14, 10<14, high=2; mid 1 → 7, 10>7, low=2; mid 2 → 9, 10>9, low=3; now low 3 > high 2, return −1. 3 steps, then the crossing.

Task 6 — pass the six tests

Write your own binary search and run it against all six boundary cases from §12.5: an empty list, a one-item list, a two-item list, the first element, the last element, and a missing value. Fix anything that fails. Which case caught the most bugs for you?

What to watch for

The two-item list and the "missing value just past the end" case are the usual culprits — they are exactly where a stray < instead of <=, or a missing −1, shows itself. If all six pass, the loop condition and the two narrowing steps are consistent.

12.10Self-check

Binary search on 1 000 000 sorted items needs at most about:

Each step halves the range; a million halves to one in about twenty steps.

You have unsorted data and need exactly one search. The right choice is:

Preparation only pays off when amortised over many queries. And the last option is silently wrong, which is worse than slow.

Binary search on unsorted data:

It happily discards the half containing your item. Silent wrongness is the most dangerous failure mode in software.

When is a sorted list with bisect better than a set?

Hash tables destroy order by design. Order questions need an ordered structure.

A binary search that writes high = middle instead of high = middle - 1 risks:

If the window never narrows, low and high never cross and the while loop never ends. Always move past the middle.

Why is the loop condition while low <= high rather than <?

With <, the last remaining candidate is never checked, so a value sitting there is missed. The trace in §12.4 ends exactly when low passes high.

12.11Homework

Due before week 13 — about three hours — and this feeds your final project

Create AA_Week12.ipynb and complete Tasks 1–6.
Reproduce §12.8 at four sizes and plot all three strategies on one log–log figure.
Write the five-sentence interpretation for the plot, naming the class of each line from its slope.
Take your working binary search from Task 6 and add an assertion or comment documenting each of the six boundary cases it survives. Keep it — you may reuse it in the final project.
Choose your final-project problem (see the course home page) and write one paragraph: the task, the data, the two approaches you intend to compare.

12.12Words from this week

Term	Meaning in plain words
linear search	Check items one at a time. O(n), no preparation needed.
binary search	Halve the sorted range each step. O(log n).
precondition	Something that must be true for an algorithm to be correct — here, "the data is sorted".
off-by-one	A boundary error — a stray ±1 or the wrong comparison — that misses an item or loops forever.
insertion point	The index where a value would go to keep the list sorted; what `bisect` returns.
preprocessing	Work done once up front (sorting, building a set) to make later queries cheap.
bisect	Python's built-in binary search, including "where would this go?".
range query	"Everything between x and y" — answerable with order, not with hashing.

12.13Chapter problem set — Skiena 2.10

Binary search runs on logarithms, so this is the natural week to meet the log rules and a cluster of Skiena's puzzles that all turn on the same idea: halving, and the number of times you can do it. Throughout, lg means log base 2.

Problem 2-39 · proving the logarithm rules

Give an accessible argument for each identity: (a) log_a(xy) = log_a x + log_a y; (b) log_a(x^y) = y · log_a x; (c) the change-of-base rule log_a x = log_b x / log_b a; and (d) x^{log_b y} = y^{log_b x}.

Worked solution

The one fact behind all four: a logarithm is just "the exponent you need". If log_a x = p, that is only shorthand for x = a^p. Keep swapping between those two ways of writing the same thing and the rules fall out.

(a) log_a(xy) = log_a x + log_a y. Write x = a^p and y = a^q. When you multiply powers of the same base you add the exponents: xy = a^p+q. So the exponent for xy is p + q, i.e. log_a(xy) = p + q = log_a x + log_a y. (This is exactly why old slide rules turned multiplication into addition.)

(b) log_a(x^y) = y · log_a x. With x = a^p, raising to the y-th power multiplies the exponent: x^y = a^py. So the exponent for x^y is py = y · log_a x.

(c) change of base. Start from x = a^p where p = log_a x. Take log base b of both sides and use rule (b): log_b x = p · log_b a. Divide across: p = log_b x / log_b a. That is the rule.

(d) x^{log_b y} = y^{log_b x}. Two things are equal when their logs are equal. Take log base b of each side (rule b): the left gives log_b y · log_b x, the right gives log_b x · log_b y. Same product, so the two sides are equal.

check_log_rules.py

import math

x, a, b = 50, 2, 10
print(math.log(x, a))                    # log base 2 of 50
print(math.log(x, b) / math.log(a, b))   # change of base — same value

# identity (d): x**(log_b y) should equal y**(log_b x)
print(3 ** math.log(8, 10))              # 2.6968...
print(8 ** math.log(3, 10))              # 2.6968... — equal

5.643856189774724 5.643856189774724 2.696844... 2.696844...

Answer: all four hold, and each is just the exponent rules read through the "log = exponent" lens. Rule (c) is the one you will use most: it says any two bases differ only by the constant factor 1 / log_b a. That constant vanishes inside Big-O — which is why the base of the log never matters for complexity, and why we can write O(log n) without ever naming a base.

Problem 2-40 · ⌈lg(n+1)⌉ = ⌊lg n⌋ + 1

Show that the ceiling of lg(n+1) equals the floor of lg n, plus one, for every integer n ≥ 1.

Worked solution

Both sides are secretly counting the same thing: how many bits n needs (equivalently, how many times you halve n before reaching 1). The interesting action is all at the powers of two, so tabulate a few values and watch the two columns agree:

n	lg n	⌊lg n⌋ + 1	lg(n+1)	⌈lg(n+1)⌉
1	0.00	1	1.00	1
2	1.00	2	1.58	2
3	1.58	2	2.00	2
4	2.00	3	2.32	3
5	2.32	3	2.58	3
6	2.58	3	2.81	3
7	2.81	3	3.00	3
8	3.00	4	3.17	4

Why it works: for any n with 2^k−1 ≤ n < 2^k, the floor ⌊lg n⌋ is k−1, so the left-hand side is k. On the same range n+1 sits in (2^k−1, 2^k], so lg(n+1) is just above k−1 and at most exactly k, and its ceiling is also k. Both sides are k. The only place to be careful is the boundary n = 2^k: there lg n is exactly k so the left side is k+1, and n+1 = 2^k+1 pushes lg(n+1) just above k so its ceiling is k+1 too — they still agree (look at the n = 2, 4, 8 rows).

Answer: both sides count the number of bits of n, so ⌈lg(n+1)⌉ = ⌊lg n⌋ + 1 for all n ≥ 1, the two ways of writing "how many halvings to reach 1".

Problem 2-41 · how many bits does n need?

Prove that the binary representation of an integer n ≥ 1 has exactly ⌊lg n⌋ + 1 bits.

Worked solution

The largest number you can write with b bits is 2^b − 1 (all ones): 1 bit reaches 1, 2 bits reach 3, 3 bits reach 7, 8 bits reach 255. So a number n needs exactly b bits when it fits in b bits but not in b−1:

2^b−1 ≤ n < 2^b

Take lg of that double inequality (lg is increasing, so it preserves order): b − 1 ≤ lg n < b. The only integer in the half-open interval [lg n, lg n + 1) whose floor sits at the bottom is b − 1 = ⌊lg n⌋, so b = ⌊lg n⌋ + 1. A small table confirms it:

n	binary	bits	⌊lg n⌋ + 1
1	1	1	0 + 1 = 1
2	10	2	1 + 1 = 2
4	100	3	2 + 1 = 3
255	11111111	8	7 + 1 = 8
256	100000000	9	8 + 1 = 9

Answer: ⌊lg n⌋ + 1 bits. This is the same quantity as problem 2-40, and it is exactly why binary search takes about lg n steps — each comparison learns one bit about where the target sits, and a number in a list of n needs ⌊lg n⌋ + 1 bits to pin down.

Problem 2-42 · a sort in O(n log √n)?

Someone shows you a sorting algorithm that runs in O(n log √n). Sorting is known to need Ω(n log n) comparisons in the worst case. How can both be true?

Worked solution

It looks like a contradiction until you simplify the log. Using rule (b) from 2-39, √n = n^1/2, so:

log √n = log(n^1/2) = ½ · log n

Therefore O(n log √n) = O(n · ½ log n) = O(½ · n log n) = O(n log n) — the one-half is a constant factor, and Big-O throws constant factors away.

Answer: nothing is broken. O(n log √n) is the very same class as O(n log n), just written in a disguise. It does not beat the Ω(n log n) lower bound — it sits right on it. A tidy reminder that "log √n" and "½ log n" are the same thing, and that constant factors never change the class.

Problem 2-46 · marbles and a 100-storey building

You want the lowest floor of a 100-storey building from which a dropped marble breaks. How few drops do you need (a) with a plentiful supply of identical marbles, and (b) with only two marbles?

Worked solution

(a) Plenty of marbles → binary search. A broken marble is no loss, so you can gamble on the middle floor every time: drop from 50. If it breaks, the answer is below 50; if not, above. Each drop halves the range, so you need ⌈lg 100⌉ = 7 drops — the same halving as every other week-12 idea.

(b) Only two marbles → you cannot binary search. If your first marble breaks at floor 50, you have one marble left and no choice but to walk it up one floor at a time from where you last knew it was safe — a linear scan. So a reckless first jump risks up to 49 further drops. The cure is to make the first marble take smaller and smaller steps, so that whichever gap it breaks in, the linear finish with the second marble is short. Drop the first marble at floors 14, then 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100 — gaps of 14, 13, 12, … shrinking by one each time.

Why 14? If the first marble breaks on drop number d, you have already spent d drops and the remaining gap to scan is 14 − d floors, for a total of about 14 every time. You want the first gap k big enough that k + (k−1) + … + 1 = k(k+1)/2 covers all 100 floors: the smallest such k is 14, because 14 × 15 / 2 = 105 ≥ 100 while 13 × 14 / 2 = 91 falls short.

Answer: 7 drops with unlimited marbles (binary search); about 14 drops worst case with just two, using the shrinking-gap (triangular- number) strategy. Two marbles cost you the logarithm — you drop from lg n to roughly √n.

Problem 2-47 · ten bags, one weighing

You have 10 bags of coins. Nine hold genuine 10-gram coins; one bag holds only 9-gram forgeries. With a digital scale that reads exact grams, identify the bad bag in a single weighing.

Worked solution

The trick is to make each bag contribute a different, recognisable amount to one pile. Number the bags 1 to 10, and take 1 coin from bag 1, 2 coins from bag 2, 3 from bag 3, …, 10 from bag 10 — 55 coins in all. If every coin were genuine the pile would weigh 55 × 10 = 550 grams. Each forged coin is 1 gram light, and bag k contributed exactly k coins, so a light bag k makes the pile read 550 − k grams. The number of grams missing is the guilty bag's number.

coin_bags.py

weights = [10] * 10          # ten bags, all 10-gram coins to start
weights[6] = 9               # bag number 7 secretly holds 9-gram coins

# take (i+1) coins from bag i (0-indexed) and weigh them all together
total = sum((i + 1) * weights[i] for i in range(10))
print(550 - total)           # 7  -> the light bag is number 7

Answer: take k coins from bag k, weigh all 55 together, and read off 550 − (reading) — that difference is the light bag's number. One weighing, no searching: a positional-counting trick that packs ten answers into a single number.

Problem 2-48 · eight balls, two weighings

You have 8 balls that look identical, but one is slightly heavier. Using a balance scale only twice, find the heavy one.

Worked solution

A balance has three outcomes each time — left heavier, right heavier, or level — so two weighings can distinguish up to 3 × 3 = 9 possibilities, and 9 ≥ 8. That count tells you it must be doable; here is how. Split the 8 balls into groups of 3, 3 and 2.

Weighing 1: put the two groups of 3 on the pans.
- If they balance, the heavy ball is one of the 2 set aside. Weigh those two against each other — the heavier pan shows it. Done in two.
- If one side is heavier, the heavy ball is among those 3.
Weighing 2 (when the heavy ball is in a group of 3): take that group and weigh any 1 against another 1. If one is heavier, that is it; if they balance, it is the third ball you did not place.

Answer: split 3 / 3 / 2 and you always finish in two weighings. It works because each weighing yields three outcomes, so two weighings carry 3² = 9 distinguishable results — comfortably more than the 8 balls you must tell apart. (The same reasoning shows you could handle up to 9 balls in two weighings, but not 10.)

Where this leads

Binary search only works on sorted data. Week 13 asks what sorting itself costs, and why the sort you invent is so much slower than the built-in one.