A First Taste of Algorithms · Lab 1: Counting Steps

5. The race

Now the measurement this lab has been building toward. We race the two searches on lists of increasing size, searching each time for the last element — the worst case for linear search:

for n in [10, 100, 1000, 10000, 100000, 1000000]:
    items = list(range(n))          # the sorted list 0, 1, ..., n-1
    target = n - 1                  # the last element
    print(n, linear_search(items, target), binary_search(items, target))

Run it and look at the table. The left column multiplies by 10 each row. The middle column does the same — linear search’s cost grows in step with the list, which is what “linear” means. The right column barely moves. A million items, about twenty steps.

Now sit with the table for a minute, because it is saying something strange. Each tenfold growth in the list adds the same small, fixed number of steps to binary search — roughly three or four per row. Multiplying the problem adds to the cost. You met a function with exactly this character in Book 2: the logarithm, the function that turns multiplication into addition. Binary search costs about log₂ n steps because each step halves the region, and “how many halvings from n down to 1” is precisely what log₂ n counts.

Deeper water. Extend the table in your head: at this rate, how many steps would binary search need on a trillion items? Write down your estimate, then test the rule “tenfold the items, add three or four steps” against it. Later, when you can prove the cost is ⌈log₂(n+1)⌉ exactly, check your estimate again. (And a question to keep: linear search never needed the list sorted. Binary search does. Sorting itself costs something — Chapter 6 asks how much, and whether the toll is worth paying. Spoiler: it depends on how many searches you plan to do, which is the kind of answer cost questions usually have.)

Break it

Predict first. Run second. Explain any gap third.

1. In binary_search, change lo = mid + 1 to lo = mid. Search the list 2, 5, 8, 13 for 21. Predict what happens before you run it — and be patient with your prediction. (When you understand what went wrong, you have understood why the + 1 is load-bearing, and you have met the most common way binary search is written incorrectly by professionals.)
2. Run binary_search on an unsorted list, searching for an element that is genuinely in it. Does it find it? Sometimes? Always? Never? Try several lists before answering. What exactly did sortedness buy?
3. In the race of §5, change the target from the last element to the first (target = 0). Predict both columns. Which algorithm’s cost changed, and what does that tell you about worst-case versus best-case as ways of describing an algorithm?
4. (Harder.) Modify linear_search so that instead of returning step counts it returns the position of the target, or -1 if absent. Then do the same for binary_search. You now have the two functions every programmer carries; Python’s own in and index are these, in dress clothes.

All 32 chapters of A First Taste of Algorithms · Foundations · All courses