A First Taste of Algorithms · Lab 1: Counting Steps

3. Searching for what isn’t there

Searching real lists, you don’t know in advance whether the target is present. Predict before running: what does the program in §2 print if you search for "Euler"?

It prints nothing. The loop ends, no message, silence. The program is not wrong, exactly — but silence is a poor answer to a question. Here is a version that always answers, packaged so we can reuse it:

def linear_search(items, target):
    steps = 0
    for item in items:
        steps = steps + 1
        if item == target:
            return steps
    return -steps  # negative means: not found, after this many steps

Two new things. def gives the procedure a name so we can call it on any list and any target without retyping it — that is all def means for now, though in Chapter 3 the ability to name a procedure will turn out to be more powerful than it looks. And return hands a value back to whoever called. Try it:

print(linear_search(["Ada", "Erdos", "Gauss", "Hua"], "Hua"))
print(linear_search(["Ada", "Erdos", "Gauss", "Hua"], "Euler"))

Notice what a miss costs: the full n steps, every time. You cannot declare something absent until you have looked everywhere. Absence is expensive — unless the list has structure. Which brings us to the chapter’s main event.

4. Binary search, measured

Chapter 1’s claim: if the list is sorted, you can find any target — or certify its absence — by repeatedly checking the middle and discarding half. Here is the claim as a program:

def binary_search(items, target):   # items must be sorted
    steps = 0
    lo = 0
    hi = len(items) - 1
    while lo <= hi:
        steps = steps + 1
        mid = (lo + hi) // 2        # // divides and drops the remainder
        if items[mid] == target:
            return steps
        if items[mid] < target:
            lo = mid + 1            # target can only be in the right half
        else:
            hi = mid - 1            # ... or the left half
    return -steps

Fifteen lines, and three small novelties: items[mid] picks out the entry at position mid (positions start at 0); len(items) is the length of the list; and while is a loop that runs as long as its condition holds — here, as long as the stretch between lo and hi hasn’t shrunk to nothing. The pair lo, hi marks the region where the target could still be. Every pass through the loop, one of the last two lines cuts that region roughly in half. That sentence is the entire algorithm; the code is just the sentence with its sleeves rolled up.

Before running anything, do one search entirely by hand. Take the sorted list 2, 5, 8, 13, 21, 34, 55, 89 and search for 21, writing down lo, hi, and mid at every step. Then run the code and check that the machine agrees with your hand. If it doesn’t, one of you is wrong, and finding out which is the best exercise in this lab.

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