Seven guesses are always enough
A friend thinks of a number from 1 to 100. You guess, and they say higher or lower.
If you guess 1, 2, 3 and so on, it could take a hundred goes. There is a way that never needs more than seven. Your phone uses the same idea to find one contact among thousands.
By the end of this lesson
Note
I can find an item with linear and binary search.
Key words
| Word | What it means | Example |
|---|---|---|
| Algorithm | a set of steps that solves a problem | |
| Linear search | checking each item in turn from the start | |
| Binary search | checking the middle and throwing away half each time | |
| Sorted | in order, smallest first | [3, 8, 12, 19] |
| Index | the position of an item in a list, counting from 0 | |
| Comparison | one test of an item against the target |
The cells students fill in are left blank in this preview.
Before you start
Note
Press Start the lab on the bar at the top. When it is ready, open JupyterLab from the bar and make a new notebook with File, New, Notebook. The code boxes on this page run here in the lesson. The Run buttons type into the lab's terminal.
Linear search checks every item in turn
A linear search starts at index 0 and compares each item with the target. It stops when it finds a match or runs out of items.
It works on any list, sorted or not. But if the target is last, or missing, it checks every single item. A list of a million songs can need a million comparisons.
A linear search through a playlist
# A playlist, in the order the songs were added.
songs = ["Rain", "Glow", "Echo", "Neon", "Tide", "Pulse"]
target = "Tide"
checks = 0
found = -1
for place in range(len(songs)):
checks = checks + 1
if songs[place] == target:
found = place
break
print("found at index", found, "after", checks, "checks")
# Change target to "Rain", then to "Storm".
# How many checks does each one take?
Binary search halves the list each time
A binary search looks at the middle item of a sorted list. If that is the target, it stops.
If the target is bigger, the whole left half can be thrown away. If it is smaller, the right half goes. Then it looks at the middle of what is left. Each comparison halves the items still in play.
Worked example: finding 37
| Step | Low | High | Middle | Item there | What happens |
|---|---|---|---|---|---|
| 1 | 0 | 10 | 5 | 31 | 37 is bigger: low becomes 6 |
| 2 | 6 | 10 | 8 | 50 | 37 is smaller: high becomes 7 |
| 3 | 6 | 7 | 6 | 37 | Found at index 6 |
The cells students fill in are left blank in this preview.
The guessing game as a binary search
# Guess a number from 1 to 100 by always guessing the middle.
secret = 73
low = 1
high = 100
guesses = 0
while low <= high:
middle = (low + high) // 2
guesses = guesses + 1
print("guess", guesses, ":", middle)
if middle == secret:
print("got it in", guesses, "guesses")
break
elif middle < secret:
low = middle + 1
else:
high = middle - 1
# Change secret to 1, then to 100.
# Does it ever take more than 7 guesses?
A common mistake
Warning
Many people think binary search works on any list. It only works when the list is sorted. Throwing away the left half is safe only because every item there is smaller. On a jumbled list it can miss an item that is there.
Timing both searches in the lab
Python can time a line of code for you with its timeit module. The two Runs below search a list of a million numbers for the last one.
The first uses in, which is a linear search. The second uses bisect, Python's own binary search. Read the time at the end of each line, and look at its unit.
Time a linear search of a million
docker exec jupyter python3 -m timeit -s "data = list(range(1000000))" "999999 in data"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Time a binary search of a million
docker exec jupyter python3 -m timeit -s "import bisect" -s "data = list(range(1000000))" "bisect.bisect_left(data, 999999)"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Type this in your notebook: both searches
def linear_search(items, target):
for place in range(len(items)):
if items[place] == target:
return place
return -1
def binary_search(items, target):
low = 0
high = len(items) - 1
while low <= high:
middle = (low + high) // 2
if items[middle] == target:
return middle
if items[middle] < target:
low = middle + 1
else:
high = middle - 1
return -1
Then this in a new cell: time them
# A million even numbers, already in order.
numbers = list(range(0, 2000000, 2))
print(linear_search(numbers, 1999998), binary_search(numbers, 1999998))
%timeit linear_search(numbers, 1999998)
%timeit binary_search(numbers, 1999998)
Going further: the worst case
A binary search of 100 items never needs more than 7 comparisons, because 2 to the power 7 is 128. Work out the most comparisons for 1,000 items, then for a million.
Check your answer in the notebook: add a counter to binary_search and search for a number that is not in the list.