← Back to the Introduction to Computer Science outline The Course Maker
← Introduction to Computer Science outline
Week 13 · Chapter

Chapter 13 — Algorithms: Searching, Sorting & Growth

Introduction to Computer Science Free sample edition

The module's primary reading · ~50–60 minutes · Objective 8 (implement and trace linear search, binary search, and selection sort; describe how an algorithm's step count grows with input size in Big-O terms; write and trace a simple recursive function; and define a class with init, attributes, and methods), Objective 4 (write while loops and for loops over range(), using counters, accumulators, nested loops, and break, and recognize and repair an infinite loop and an off-by-one error) · Read it first this week; the lecture, the slides, the tutorial, the quiz, and the Coding Lab all build on it.

In plain language

Two programs can print the same answer while one does far less work than the other, and this week you learn to see the difference. A search (a program that looks through a list for one value) can check every item in turn, or it can keep cutting a sorted list in half. A sort (a program that puts a list in order) can do its work pass by pass, and you can count every check it makes. Counting those checks tells you how a program's work grows (how fast the work rises as the list gets longer), and a short label called Big-O names that pattern. As always, you predict what each program prints and then run it to check.

Why you already care about this

Think of the last time you hunted for one page in a thick printed book. You did not start at page 1 and turn every page. You opened near the middle, saw page 212, and flipped back because you wanted page 87. Two or three flips later you were there. A friend who turned every page from the front would also find page 87, but only after 86 page turns.

Or play the number game with someone. They think of a whole number from 1 to 100, and after each guess they say "higher" or "lower." Guess 50 first, then 25 or 75, and keep halving. Later in this chapter, a run shows that halving never needs more than 7 guesses for 100 numbers. Guessing 1, 2, 3, and so on could take 100.

Both players get the right answer. One of them does a tiny fraction of the work. This chapter turns that hunch into programs you can run and counts you can trust. It also shows you the catch: halving only works when the items are in order, so sorting comes first, and sorting has a cost of its own.

By the end of this chapter you will be able to:

  • write and trace a linear search that returns an index or -1;
  • count comparisons as a measure of work that is the same on every machine;
  • write and trace a binary search with lo, hi, and mid on a sorted list;
  • explain why binary search needs a sorted list, and when linear search wins anyway;
  • test a search on both ends and on missing values, and catch an off-by-one;
  • trace selection sort pass by pass and count its comparisons;
  • name a step count's growth class: constant, logarithmic, linear, or quadratic.

Carry this line with you: count the steps; never trust the stopwatch.

Where we are

  • Already covered: Week 5 gave you while loops, counters, and the off-by-one error; Week 6, for loops and nested loops; Week 7, functions that return a value; Week 9, lists and sorted(); Week 10, tuples and the swap.
  • This week: linear search, binary search and its sorted-list precondition, counting comparisons, testing a search on its ends, selection sort, and the growth classes of Big-O.
  • How they connect: every search and sort here is a loop over a list inside a function, with a counter that adds one per comparison, and a search hands back its answer as a tuple.
  • Where we're going next: Week 14, Recursion, shows a function that calls itself, and the halving inside binary search is one of the places where that idea reads naturally.

Four earlier ideas carry most of the weight. From Week 5, a counter starts before a loop and adds one on each pass, and < versus <= decides whether the last value gets its turn. From Week 6, the inner loop of a nested pair runs to completion on every pass of the outer loop. From Week 9, pages[4] reads the item at index 4, and sorted() returns a new sorted list. From Week 10, a, b = b, a swaps two values, and return i, comparisons hands back one tuple of two values. Spend extra time on Sections 3 and 5. The second half of the term leans on both.

1. Check every item in turn: linear search

A teacher looking for one student's quiz in a stack of 30 often starts at the top and checks each sheet until the right name appears. Nothing about the stack needs to be in order. The cost is that a missing quiz means checking all 30 sheets before you can say it is not there.

Linear search is a search that checks the items of a list one at a time from the front until it finds the target or runs out of items; it works on any list, sorted or not.

The target is the value a search is looking for, handed to the search function as an argument, as in binary_search(pages, 21), where 21 is the target.

Your reading log now keeps eight daily page counts, sorted from smallest to largest. This chapter calls the list pages. A linear search hands back two things as one tuple: the index where it found the target, and how many comparisons it made. When the target is not there, it hands back -1 for the index, the same "not found" signal that find() gave you in Week 11.

Worked example — the pinned linear search. This program prints every comparison as it makes it. Predict the last line of each of the three searches before you read the output.

def linear_search(items, target):
    comparisons = 0
    for i in range(len(items)):
        comparisons = comparisons + 1
        print("compare", items[i], "at index", i)
        if items[i] == target:
            return i, comparisons
    return -1, comparisons

pages = [3, 8, 12, 15, 21, 27, 34, 40]
print(linear_search(pages, 21))
print(linear_search(pages, 3))
print(linear_search(pages, 22))

Output

compare 3 at index 0
compare 8 at index 1
compare 12 at index 2
compare 15 at index 3
compare 21 at index 4
(4, 5)
compare 3 at index 0
(0, 1)
compare 3 at index 0
compare 8 at index 1
compare 12 at index 2
compare 15 at index 3
compare 21 at index 4
compare 27 at index 5
compare 34 at index 6
compare 40 at index 7
(-1, 8)

Here is the trace.

  1. For 21, the loop checks index 0, 1, 2, 3, and 4. At index 4 the test items[i] == target is True, so return hands back (4, 5) and the call ends at once.
  2. For 3, the first check matches, so the call ends after one comparison: (0, 1).
  3. For 22, no check matches. The loop runs out after index 7, and the last line of the function hands back (-1, 8).

In words: the 21 sat at index 4 and took 5 comparisons, and the missing 22 cost all 8.

Misconception check. Students often think a search that finds nothing has done no work. That is tempting, because it found nothing to show you. But a missing target is the most expensive case for linear search: it must check every item before it can say no. The cure: when you predict a linear search's comparisons, ask first whether the target is there at all.

In practice (your tools). Paste the program into your free browser Python runner and press Run. Then change the last call to look for 40 and predict the count before you run it. To watch the loop variable i move, paste the program into Python Tutor at pythontutor.com and step forward with Next.

Memory hook: linear search reads the stack from the top.

2. Count comparisons, not seconds

Two friends race to find a name in the same list, one on a new laptop and one on an old phone. The laptop wins the race. Does that mean its method is better? It does not. The faster machine would win with the worse method too. To compare two methods fairly, you need a measure that does not depend on the machine.

A comparison counter is an accumulator that adds one each time a search or sort compares two values, so the program reports how much work it did as a count that is the same on every machine.

You already know this tool. The line comparisons = comparisons + 1 is the accumulator pattern from Week 5, placed right where each comparison happens. A clock reading changes with the machine, with other programs running, and from one run to the next. A count of comparisons never does. That is why this course never grades a timing.

Worked example — the pinned head-to-head. This program runs a linear search and a binary search on the sorted list 1 to 16 and prints each result as (index, comparisons). Section 3 explains how binary search works; here, look only at the counts.

def linear_search(items, target):
    comparisons = 0
    for i in range(len(items)):
        comparisons = comparisons + 1
        if items[i] == target:
            return i, comparisons
    return -1, comparisons

def binary_search(items, target):
    lo = 0
    hi = len(items) - 1
    comparisons = 0
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        comparisons = comparisons + 1
        if items[mid] == target:
            return mid, comparisons
        elif items[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1, comparisons

numbers = list(range(1, 17))
print(linear_search(numbers, 13))
print(binary_search(numbers, 13))
print(linear_search(numbers, 16))
print(binary_search(numbers, 16))

Output

(12, 13)
(12, 4)
(15, 16)
(15, 5)

Both searches found 13 at index 12. Linear search needed 13 comparisons; binary search needed 4. For 16, the last item, it was 16 comparisons versus 5. Linear search checked 1, 2, 3, and on up to 13. Binary search checked only the middle items 8, 12, 14, and 13. Its first middle index is 0 + (15 − 0) // 2 = 7, which holds 8.

Misconception check. Students often think speed can only be measured with a clock. That is tempting, because "fast" sounds like a time. But a time measures the machine as much as the method. The cure: count the comparisons, and you have a number that is the same on every machine and for every run.

In practice (your tools). In your browser runner, paste the head-to-head program and add one more pair of lines that search for 1. Predict both counts before you run it. Honesty note: your runner may show how long a program took, but this course never keys a timing, because the same program can report a different time on the next run.

Memory hook: a count travels; a clock stays home.

3. Halve the list: binary search

Back to the printed book. You open in the middle and look at the page number. If your page is higher, you never look at the first half again. If it is lower, you never look at the second half. Each look throws away half of what is left.

Binary search is a search on a sorted list that compares the target with the middle item and throws away the half that cannot hold it, repeating until it finds the target or no items are left.

The program keeps two names for the ends of the part still in play. lo is the lowest index that could still hold the target, and hi is the highest. The middle index is mid = lo + (hi - lo) // 2. The // is floor division from Week 2, so the middle is always a whole index. The loop runs while lo <= hi:, in words, as long as the low end is less than or equal to the high end. When lo passes hi, nothing is left to check.

Worked example — the pinned binary search, traced. This version prints lo, hi, mid, and the middle value on every pass. Predict the middle values for 21 first.

def binary_search(items, target):
    lo = 0
    hi = len(items) - 1
    comparisons = 0
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        comparisons = comparisons + 1
        print("lo", lo, "hi", hi, "mid", mid, "value", items[mid])
        if items[mid] == target:
            return mid, comparisons
        elif items[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1, comparisons

pages = [3, 8, 12, 15, 21, 27, 34, 40]
print(binary_search(pages, 21))
print(binary_search(pages, 3))
print(binary_search(pages, 22))

Output

lo 0 hi 7 mid 3 value 15
lo 4 hi 7 mid 5 value 27
lo 4 hi 4 mid 4 value 21
(4, 3)
lo 0 hi 7 mid 3 value 15
lo 0 hi 2 mid 1 value 8
lo 0 hi 0 mid 0 value 3
(0, 3)
lo 0 hi 7 mid 3 value 15
lo 4 hi 7 mid 5 value 27
lo 4 hi 4 mid 4 value 21
(-1, 3)

Here is the trace for 21, step by step.

  1. The list has 8 items, so lo is 0 and hi is 8 − 1 = 7. The middle index is 0 + (7 − 0) // 2 = 3, which holds 15.
  2. Since 15 is less than 21, the target can only be to the right, so lo becomes 3 + 1 = 4. The next middle index is 4 + (7 − 4) // 2 = 5, which holds 27.
  3. Since 27 is more than 21, the target can only be to the left, so hi becomes 5 − 1 = 4. Now lo and hi are both 4, the middle index is 4, and it holds 21. The call returns (4, 3).

For 3, the search went left every time, through middle indexes 3, 1, and 0. For 22, it checked 15, 27, and 21; then lo became 5 while hi was 4, so the loop stopped and returned (-1, 3). In words: binary search found 21 in 3 comparisons, where linear search took 5.

Your running reading log program now has this function in it. Its Week 13 stage is the same code without the print line inside the loop, and it prints the three results (4, 3), (0, 3), and (-1, 3).

Misconception check. Students often think binary search starts at the front and skips ahead, so they predict mid as 0 or 1 on the first pass. That is tempting, because every loop so far started at index 0. But binary search starts in the middle, at index 3 for eight items, and moves lo or hi past the middle each time. The cure: write lo, hi, and mid in a three-column table, one row per pass, before you run anything.

In practice (your tools). Paste the traced program into Python Tutor and step through the search for 22. Watch lo and hi close in on each other until lo is 5 and hi is 4, and the loop test turns False.

Memory hook: look in the middle, then throw half away.

4. Sort first: the precondition of binary search

Halving the book works because the pages are numbered in order. Shuffle the pages, open to the middle, and see page 212. Is page 87 to the left? You cannot know. Halving needs order.

A precondition is something that must already be true before an algorithm runs for it to work correctly; binary search's precondition is that the list is sorted.

Worked example — the pinned unsorted list. This version of binary search returns only the index. Predict both lines.

def binary_search(items, target):
    lo = 0
    hi = len(items) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if items[mid] == target:
            return mid
        elif items[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

data = [27, 8, 40, 3, 15]
print(binary_search(data, 3))
print(binary_search(sorted(data), 3))

Output

-1
0

The 3 is in data, at index 3, yet the first search printed -1. Here is why. The middle index is 2, which holds 40. Since 40 is more than 3, the search threw away everything to the right of index 2, including the 3. The search did exactly what it was written to do, on a list that broke its precondition. sorted(data) is [3, 8, 15, 27, 40], and on that list the 3 is at index 0.

That is a logic error, not a crash. No exception appears, and nothing in red tells you something went wrong. The program runs and prints the wrong thing.

Binary search is not always faster, either. In Section 3 the 3 at the front of pages took binary search 3 comparisons, while in Section 1 linear search found it in 1. On a tiny list, or for a target near the front, the plain method can win.

Misconception check. Students often think binary search works on any list, because the code never checks whether the list is sorted. That is tempting, because nothing stops you from calling it on a shuffled list. But the code trusts its precondition and quietly gives a wrong -1 when it fails. The cure: sort first with sorted(), or use linear search, which needs no order at all.

In practice (your tools). In your browser runner, paste the unsorted program and add a third line that searches data for 27. Predict whether it finds 27 before you run it, then explain the run by tracing mid by hand. The Standard Library reference on docs.python.org describes sorted() under its built-in functions.

Memory hook: halving needs order.

5. Test the ends: a binary search that looks right

A recipe that works for a dozen cookies can still fail for one cookie or for a hundred. A careful baker tries the small case and the large case. A careful programmer does the same, because a search can look right and still break at the edges.

Binary search has a famous history of this. Bentley's Programming Pearls (1986) records that the first binary search was published in 1946, and that the first one correct for every list length did not appear until 1962. Much later, Bloch's 2006 note reported that a widely used library's binary search had carried a bug in its middle-index line for about nine years. That line added the two ends together before halving them, and in a language with a size limit on whole numbers, the sum could grow past the limit. Python's integers never overflow, as Week 2 showed, but the course writes lo + (hi - lo) // 2 anyway, because that form is safe in every language. The lesson for you is broader than one line: a binary search that looks right is a claim, and runs are the evidence.

The worst case is the input of a given size that makes an algorithm do the most work, such as a target that is missing from the list, which makes linear search check every item.

Worked example — testing the ends. This program runs the correct binary search, with its comparison counter, on the first item, the last item, a value smaller than every item, and a value larger than every item. Predict all four lines.

def binary_search(items, target):
    lo = 0
    hi = len(items) - 1
    comparisons = 0
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        comparisons = comparisons + 1
        if items[mid] == target:
            return mid, comparisons
        elif items[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1, comparisons

pages = [3, 8, 12, 15, 21, 27, 34, 40]
print(binary_search(pages, 3))
print(binary_search(pages, 40))
print(binary_search(pages, 2))
print(binary_search(pages, 41))

Output

(0, 3)
(7, 4)
(-1, 3)
(-1, 4)

All four answers are right. Finding the last item, 40, took 4 comparisons, one more than finding 21, because the search had to walk the right-hand side down to a single item.

Now change one character's worth of thinking. Suppose the first line inside the function says hi = len(items) instead of hi = len(items) - 1. It looks harmless.

Worked example — the off-by-one. Predict both lines.

def binary_search(items, target):
    lo = 0
    hi = len(items)
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if items[mid] == target:
            return mid
        elif items[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

pages = [3, 8, 12, 15, 21, 27, 34, 40]
print(binary_search(pages, 21))
print(binary_search(pages, 41))

Output

4
IndexError

The search for 21 still worked, which is exactly why this bug survives a quick test. The search for 41 kept moving right. lo became 5, then 7, then 8, while hi stayed 8. The loop test lo <= hi was still True, so mid became 8. The list has indexes 0 to 7, so items[8] raised IndexError. Read from the last line, the error names the type; the bug is the starting value of hi, one past the last real index.

Misconception check. Students often think a search that finds one value correctly is correct. That is tempting, because the first test passed. But bound mistakes hide at the edges, and a single test in the middle never reaches them. The cure: test the first item, the last item, a value below every item, and a value above every item, every time.

In practice (your tools). Ask your approved chatbot to write a binary search in Python that returns the index of a target or -1. Before you trust it, paste its code into your browser runner and run it on pages for 3, 40, 2, and 41, the four tests above. If any line raises an error or prints a wrong index, name the line that causes it. Caveat: a chatbot's code that passes your four tests is better evidence than its explanation, but it is still only as good as the tests you chose.

Memory hook: test both ends and one missing value on each side.

6. Sort pass by pass: selection sort

Picture lining up five friends by height for a photo. One plain way: find the shortest person and walk them to the first spot. Then find the shortest of the people left and walk them to the second spot. Keep going until everyone is placed.

Selection sort is a sorting algorithm that, on each pass, finds the smallest item not yet in place and swaps it into the next position, so the sorted part at the front grows by one item per pass.

The code is a nested loop from Week 6. The outer loop picks the place to fill, index i. The inner loop runs to completion on every pass of the outer loop, scanning everything after i to find the index of the smallest item. Then the one-line swap from Week 10, items[i], items[smallest] = items[smallest], items[i], trades the two items. The first line inside the function, items = items[:], makes a copy, so the caller's list is left alone; you met that alias-versus-copy difference in Week 9.

Worked example — the pinned selection-sort trace. Predict the list after pass 1 and pass 3.

def selection_sort(items):
    items = items[:]
    for i in range(len(items)):
        smallest = i
        for j in range(i + 1, len(items)):
            if items[j] < items[smallest]:
                smallest = j
        items[i], items[smallest] = items[smallest], items[i]
        print("pass", i + 1, items)
    return items

print(selection_sort([27, 8, 40, 3, 15]))

Output

pass 1 [3, 8, 40, 27, 15]
pass 2 [3, 8, 40, 27, 15]
pass 3 [3, 8, 15, 27, 40]
pass 4 [3, 8, 15, 27, 40]
pass 5 [3, 8, 15, 27, 40]
[3, 8, 15, 27, 40]

Here is the trace.

  1. Pass 1 fills index 0. The smallest of all five items is 3, at index 3, so 27 and 3 trade places.
  2. Pass 2 fills index 1. The smallest of what is left is 8, already at index 1, so it swaps with itself and the list does not change.
  3. Pass 3 fills index 2. The smallest of 40, 27, and 15 is 15, so 40 and 15 trade places.
  4. Passes 4 and 5 find their smallest items already in place. The last pass always does, because a single remaining item is already where it belongs.

In words: three of the five passes changed nothing you can see, but each pass still did its scan.

Worked example — a step counter. This illustrative program sorts four days of step counts with the same function. Predict pass 2.

def selection_sort(items):
    items = items[:]
    for i in range(len(items)):
        smallest = i
        for j in range(i + 1, len(items)):
            if items[j] < items[smallest]:
                smallest = j
        items[i], items[smallest] = items[smallest], items[i]
        print("pass", i + 1, items)
    return items

steps = [6400, 2100, 8800, 4300]
print(selection_sort(steps))
print(steps)

Output

pass 1 [2100, 6400, 8800, 4300]
pass 2 [2100, 4300, 8800, 6400]
pass 3 [2100, 4300, 6400, 8800]
pass 4 [2100, 4300, 6400, 8800]
[2100, 4300, 6400, 8800]
[6400, 2100, 8800, 4300]

Pass 2 found 4300 as the smallest of 6400, 8800, and 4300 and swapped it into index 1. The last line shows that steps itself never changed, because the function sorted a copy.

Misconception check. Students often think a pass that changes nothing was skipped. That is tempting, because the printed list looks the same. But the inner loop still compared every remaining item to find the smallest. The cure: count the work by the comparisons the loops make, not by the changes you can see.

In practice (your tools). Paste the pinned trace into Python Tutor and step through pass 1. Watch smallest change from 0 to 1 to 3 as j walks the list, and watch the swap trade two items in one step.

Memory hook: find the smallest, swap it forward, repeat.

7. Count the sort's comparisons

Back to the photo line. With 5 friends, the first scan compares 4 people, the next 3, then 2, then 1. That is 4 + 3 + 2 + 1 = 10 comparisons. Add more friends and the scans get longer and more numerous at the same time.

Worked example — the pinned comparison count. This program counts selection sort's comparisons on 5, 10, and 20 items. Predict the first line from the photo line above.

def count_comparisons(items):
    items = items[:]
    comparisons = 0
    for i in range(len(items)):
        smallest = i
        for j in range(i + 1, len(items)):
            comparisons = comparisons + 1
            if items[j] < items[smallest]:
                smallest = j
        items[i], items[smallest] = items[smallest], items[i]
    return comparisons

print(count_comparisons([27, 8, 40, 3, 15]))
print(count_comparisons(list(range(10, 0, -1))))
print(count_comparisons(list(range(20, 0, -1))))

Output

10
45
190

The counts follow the formula n(n − 1) ⁄ 2, where n is the number of items:

  • 5 × 4 ÷ 2 = 10
  • 10 × 9 ÷ 2 = 45
  • 20 × 19 ÷ 2 = 190

Doubling the list from 10 to 20 items took the work from 45 to 190. Since 190 ÷ 45 is about 4.2, twice the list cost about four times the comparisons. That is quadratic growth as a number, before it has a name.

Worked example — an already sorted list. Predict whether a list that is already in order costs fewer comparisons.

def count_comparisons(items):
    items = items[:]
    comparisons = 0
    for i in range(len(items)):
        smallest = i
        for j in range(i + 1, len(items)):
            comparisons = comparisons + 1
            if items[j] < items[smallest]:
                smallest = j
        items[i], items[smallest] = items[smallest], items[i]
    return comparisons

print(count_comparisons([3, 8, 15, 27, 40]))
print(count_comparisons([27, 8, 40, 3, 15]))

Output

10
10

Both lists cost 10 comparisons. The inner loop has no way to stop early, so selection sort does the same work whatever order the items start in.

Misconception check. Students often think a list that is already sorted takes no work to sort. That is tempting, because there is nothing to fix. But selection sort cannot know the list is sorted without scanning it, and its scans never stop early. The cure: predict selection sort's comparisons from n alone, with n(n − 1) ⁄ 2.

In practice (your tools). In your browser runner, add a line that counts the comparisons for list(range(40, 0, -1)). Predict it first with the formula, 40 × 39 ÷ 2, then run it. Faster sorts exist, and how they work comes in a later course.

Memory hook: double the list, quadruple the sort.

8. Name the growth: Big-O

Say you walk to class. Doubling the distance doubles the walk. Now say you sign a birthday card for everyone in a club, and every member signs a card for every other member. Doubling the club roughly quadruples the cards. And looking up one friend's number on your phone takes about the same moment whether you have 50 contacts or 500. Three different patterns of growth.

A growth class is the pattern by which an algorithm's step count rises as its input grows, such as staying flat, rising by about one when the input doubles, doubling, or quadrupling.

Big-O is a way of naming an algorithm's growth class, such as O(n) for linear growth, that describes how the step count grows with the input size n rather than giving the exact count.

This week's programs show four growth classes:

  • Constant time is growth class O(1): the step count stays the same however long the list is, as when a program reads one item by its index.
  • Logarithmic time is growth class O(log n): the step count rises by about one each time the list doubles, about log base 2 of n steps, as in binary search.
  • Linear time is growth class O(n): the step count grows in proportion to the list, so doubling the list doubles the worst-case count, as in linear search.
  • Quadratic time is growth class O(n²): the step count grows with the square of the list's length, so doubling the list roughly quadruples the count, as in selection sort's n(n − 1) ⁄ 2 comparisons.

Worked example — reading one item. Predict both lines.

pages = [3, 8, 12, 15, 21, 27, 34, 40]
print(pages[4])
print(len(pages))

Output

21
8

Reading pages[4] is one step. It would still be one step if the list held a thousand numbers, because Python goes straight to index 4. That is constant time.

Worked example — doubling the searches. This program searches for the last item of the lists 1 to 8, 1 to 16, and 1 to 32, and prints each length with its linear and binary results. Predict the comparison counts.

def linear_search(items, target):
    comparisons = 0
    for i in range(len(items)):
        comparisons = comparisons + 1
        if items[i] == target:
            return i, comparisons
    return -1, comparisons

def binary_search(items, target):
    lo = 0
    hi = len(items) - 1
    comparisons = 0
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        comparisons = comparisons + 1
        if items[mid] == target:
            return mid, comparisons
        elif items[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1, comparisons

for n in [8, 16, 32]:
    numbers = list(range(1, n + 1))
    print(n, linear_search(numbers, n), binary_search(numbers, n))

Output

8 (7, 8) (7, 4)
16 (15, 16) (15, 5)
32 (31, 32) (31, 6)

Read the counts down each column. Linear search went 8, 16, 32: each doubling of the list doubled the work, which is linear time. Binary search went 4, 5, 6: each doubling added one step, which is logarithmic time. Selection sort, from Section 7, went from 45 to 190 when its list doubled, which is quadratic time.

Worked example — the number game. This illustrative program plays every possible secret number from 1 to 100 against binary search and keeps the largest guess count.

def binary_search(items, target):
    lo = 0
    hi = len(items) - 1
    comparisons = 0
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        comparisons = comparisons + 1
        if items[mid] == target:
            return mid, comparisons
        elif items[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1, comparisons

numbers = list(range(1, 101))
most = 0
for target in numbers:
    index, count = binary_search(numbers, target)
    if count > most:
        most = count
print(most)

Output

7

Halving never needed more than 7 guesses for 100 numbers. Doubling to 200 numbers would add only about one more.

Big-O names the growth, not the count. Binary search found 13 in 4 comparisons and 16 in 5, and both are logarithmic time. That is why this course never keys a constant in front of a Big-O label, and never a time in seconds.

Misconception check. Students often think Big-O is the exact step count, so O(n) for 16 items must mean exactly 16 steps. That is tempting, because linear search's worst case on 16 items was 16. But Big-O describes how the count grows when the list grows; finding 13 took 13 steps and is still linear time. The cure: read a growth class from what happens when n doubles, not from one count.

In practice (your tools). Ask your approved chatbot how many comparisons binary search needs for a list of 64 items, and how many seconds that takes. Then add 64 to the list in the doubling program and run it. Compare its count with the chatbot's claim, and note that the seconds question has no answer this course will accept, because a time depends on the machine. Merge sort and quicksort, two faster sorts, come later in a second course.

Pause and choose one of these to think about before you read on:

  • (a) Think of a list you search often, such as the songs on your phone, the contacts in your messages, or the files in a class folder. Is it kept in order, and would linear search or binary search fit the way you look through it?
  • (b) Think of a task in your own life whose work grows faster than its size, such as everyone in a group greeting everyone else. What happens to the work when the group doubles, and which growth class does that match?

Memory hook: Big-O asks what happens when the list doubles.

Key terms

  • linear search — A search that checks the items of a list one at a time from the front until it finds the target or runs out of items; it works on any list, sorted or not. (first used: 1. Check every item in turn: linear search)
  • target — The value a search is looking for, handed to the search function as an argument, as in binary_search(pages, 21), where 21 is the target. (first used: 1. Check every item in turn: linear search)
  • comparison counter — An accumulator that adds one each time a search or sort compares two values, so the program reports how much work it did as a count that is the same on every machine. (first used: 2. Count comparisons, not seconds)
  • binary search — A search on a sorted list that compares the target with the middle item and throws away the half that cannot hold it, repeating until it finds the target or no items are left. (first used: 3. Halve the list: binary search)
  • precondition — Something that must already be true before an algorithm runs for it to work correctly; binary search's precondition is that the list is sorted. (first used: 4. Sort first: the precondition of binary search)
  • worst case — The input of a given size that makes an algorithm do the most work, such as a target that is missing from the list, which makes linear search check every item. (first used: 5. Test the ends: a binary search that looks right)
  • selection sort — A sorting algorithm that, on each pass, finds the smallest item not yet in place and swaps it into the next position, so the sorted part at the front grows by one item per pass. (first used: 6. Sort pass by pass: selection sort)
  • growth class — The pattern by which an algorithm's step count rises as its input grows, such as staying flat, rising by about one when the input doubles, doubling, or quadrupling. (first used: 8. Name the growth: Big-O)
  • Big-O — A way of naming an algorithm's growth class, such as O(n) for linear growth, that describes how the step count grows with the input size n rather than giving the exact count. (first used: 8. Name the growth: Big-O)
  • constant time — Growth class O(1): the step count stays the same however long the list is, as when a program reads one item by its index. (first used: 8. Name the growth: Big-O)
  • logarithmic time — Growth class O(log n): the step count rises by about one each time the list doubles, about log base 2 of n steps, as in binary search. (first used: 8. Name the growth: Big-O)
  • linear time — Growth class O(n): the step count grows in proportion to the list, so doubling the list doubles the worst-case count, as in linear search. (first used: 8. Name the growth: Big-O)
  • quadratic time — Growth class O(n²): the step count grows with the square of the list's length, so doubling the list roughly quadruples the count, as in selection sort's n(n − 1) ⁄ 2 comparisons. (first used: 8. Name the growth: Big-O)

Summary

  • Linear search checks items in order and returns an index or -1.
  • A missing target is linear search's worst case: every item is checked.
  • Count comparisons, not seconds; the count is the same on every machine.
  • Binary search compares with the middle and throws away half.
  • Binary search needs a sorted list; on an unsorted one it can miss a present item.
  • Test a search on the first item, the last item, and values outside the list.
  • hi = len(items) with while lo <= hi can index past the end.
  • Selection sort swaps the smallest remaining item forward on each pass.
  • Selection sort makes n(n − 1) ⁄ 2 comparisons whatever the starting order.
  • Constant, logarithmic, linear, quadratic: read the class from what doubling does.

Check your understanding

Work these before looking at the answers — they are ungraded, and the answers (with reasoning) are at the bottom of the page.

  1. A bike-share app in an illustrative example keeps its dock numbers sorted: docks = [2, 5, 9, 14, 20, 26, 31]. Using this chapter's counting versions, predict what linear_search(docks, 26) and binary_search(docks, 26) print.
  2. A weather log in an illustrative example keeps five daily highs in the order they were recorded: temps = [18, 25, 12, 30, 21]. The counting binary_search(temps, 25) prints (-1, 2), and binary_search(sorted(temps), 25) prints (3, 2). Explain the first result by tracing mid.
  3. Predict the list after each pass of selection_sort([7, 2, 9, 4]), and say how many comparisons the inner loop makes in total.
  4. Selection sort makes 15 comparisons on 6 items. Predict its comparisons on 12 items, and predict binary search's worst case on the list 1 to 64, given that it is 6 on the list 1 to 32.

Answers (worked reasoning — read after attempting)

  1. Linear search prints (5, 6): it checks 2, 5, 9, 14, 20, and then 26 at index 5, six comparisons. Binary search prints (5, 2): lo is 0 and hi is 6, so the first middle index is 0 + (6 − 0) // 2 = 3, which holds 14. Since 14 is less than 26, lo becomes 4, the next middle index is 4 + (6 − 4) // 2 = 5, and index 5 holds 26.
  2. The list breaks binary search's precondition. The first middle index is 0 + (4 − 0) // 2 = 2, which holds 12. Since 12 is less than 25, lo becomes 3 and the 25 at index 1 is thrown away. The next middle index is 3 + (4 − 3) // 2 = 3, which holds 30; since 30 is more than 25, hi becomes 2, lo passes hi, and the search returns (-1, 2). Sorted, the list is [12, 18, 21, 25, 30], and 25 is found at index 3.
  3. Pass 1 gives [2, 7, 9, 4], pass 2 gives [2, 4, 9, 7], pass 3 gives [2, 4, 7, 9], and pass 4 leaves [2, 4, 7, 9] unchanged. The inner loop compares 3, then 2, then 1, then 0 items: 3 + 2 + 1 = 6 comparisons, which matches 4 × 3 ÷ 2 = 6.
  4. On 12 items selection sort makes 12 × 11 ÷ 2 = 66 comparisons; doubling from 6 to 12 items took the work from 15 to 66, about four times as much, because the growth is quadratic. Binary search on 1 to 64 needs 7 comparisons for the last item, one more than on 1 to 32, because logarithmic growth adds about one step per doubling; a run of the doubling program with 64 confirms (63, 7).

Next up in this module: the Readings & Resources page, the lecture tutorial, the practice set, and the quiz — and next week, recursion gives you a function that calls itself, the same halving rule that drives binary search.

Built with The Course Maker · samples.thecoursemaker.com