Track: How Computers Work · Lesson 9 of 10 · Ages: 8+ · Time: 40 minutes
Computers have to find things all the time: a song in a huge music collection, a word in a dictionary, a name on a long list. If they looked at every single item one at a time, it could take ages. Luckily there is a much smarter way, and you can learn it by playing a guessing game.
Beep says A good algorithm is a set of steps that solves a problem. I love algorithms. They are like recipes for robots. Beep boop!
What you need
- Paper and a pencil.
- A friend or grown-up for the guessing game.
- About 40 minutes.
The guessing game
Ask your friend to secretly think of a number from 1 to 100. Your job is to guess it. After every guess, your friend says “higher”, “lower” or “correct”.
There are two ways to play.
Way 1: guess in order. You say 1, then 2, then 3, and so on. This is called linear search, because you go along the line, one by one. It works. But if the number is 73, you need 73 guesses!
Way 2: cut it in half. You guess the number in the middle, 50. If your friend says “higher”, you know the answer is between 51 and 100, so you have thrown away half of the numbers in one guess! Next you guess the middle of what is left, 75. Then you halve it again, and again. This is called binary search. “Binary” here means two, because each guess splits the numbers into two halves.
Pixel says Way 2 only works because the numbers are in order. If they were jumbled up, “higher” and “lower” would mean nothing. Order is the secret ingredient. Meow!
Finding 73
Here is how binary search finds 73 among the numbers 1 to 100.
| Guess | Number guessed | Answer |
|---|---|---|
| 1 | 50 | higher |
| 2 | 75 | lower |
| 3 | 62 | higher |
| 4 | 68 | higher |
| 5 | 71 | higher |
| 6 | 73 | correct! |
Only 6 guesses instead of 73!
How fast is that?
Every guess cuts the numbers in half. That adds up quickly:
- Among 100 numbers, you need at most 7 guesses.
- Among 1,000 numbers, at most 10 guesses.
- Among 1,000,000 numbers, at most 20 guesses.
Imagine looking for a name in a list of a million. Going one by one could take a million steps. Binary search needs only 20!
Let Python count the guesses
This program searches the sorted list of numbers 1 to 100 for 73, once with each method, and counts the guesses.
numbers = list(range(1, 101))
target = 73
linear_guesses = 0
for number in numbers:
linear_guesses = linear_guesses + 1
if number == target:
break
low = 0
high = len(numbers) - 1
binary_guesses = 0
while low <= high:
middle = (low + high) // 2
binary_guesses = binary_guesses + 1
if numbers[middle] == target:
break
elif numbers[middle] < target:
low = middle + 1
else:
high = middle - 1
print("Linear search guesses:", linear_guesses)
print("Binary search guesses:", binary_guesses)
print(sorted([42, 7, 19, 3]))Linear search guesses: 73 Binary search guesses: 6 [3, 7, 19, 42]
In the first part, the loop goes through the numbers in order, counting each one. The break command stops the loop as soon as 73 is found.
The second part is binary search. The variables low and high mark the part of the list that is still possible. Each time round, the program looks at the middle item. If it is too small, low moves up past the middle. If it is too big, high moves down below the middle. So the range shrinks by half each time.
The last line uses Python’s sorted, which puts a list in order for us.
Getting things in order
Binary search needs the list to be sorted. Sorting means putting things in order, like numbers from smallest to biggest or names from A to Z. Here is one easy way to sort a few number cards by hand:
1. Look at all the cards. Find the smallest one. 2. Put it at the front of a new row. 3. Look at the cards that are left. Find the smallest one. 4. Put it next in the row. 5. Keep going until no cards are left.
Sorting takes some work, but it only has to be done once. After that, you can search again and again very quickly. That is why dictionaries and phone books are in alphabetical order.
Did you know? When you search for something on a computer or phone, the computer often uses clever tricks like these, with information kept in order, so that it can find your answer in a fraction of a second.
Challenges
Try it Play the guessing game with a friend, using binary search. Pick a number from 1 to 100 and see if you can guess it in 7 guesses or fewer. Then play with the numbers 1 to 1000. Can you manage in 10?
Try it Change target = 73 to target = 1. Which search is faster now? Try it before you run it!
Show the answer
Linear search finds 1 on the very first guess. Binary search takes 6 guesses, because it starts in the middle and works its way down. So the smart method is not always faster! But for a number far along the list, binary search wins by a lot.
Try it Use the card sorting recipe to put these numbers in order: 8, 3, 9, 1, 5.
Show the answer
Smallest first: 1, then 3, then 5, then 8, then 9. The sorted row is 1, 3, 5, 8, 9.
Grown-ups Searching and sorting are classic computer science topics, and the guessing game is the best way to feel the difference between them. Children often discover binary search on their own after a few rounds. If you want to go further, try finding a word in a printed dictionary by opening it in the middle each time.
What you learned
- An algorithm is a set of steps that solves a problem.
- Linear search checks one item at a time, from the start.
- Binary search checks the middle and throws away half each time, but it only works on a sorted list.
- Binary search needs at most 7 guesses for 100 items and 20 guesses for a million items.
- Sorting puts things in order, so searching gets easier.