Algorithms: finding fast · Computer Basics
Your friend picks a number from 1 to 100 and only answers "higher" or "lower". What's the fastest way to find it?
Course contentsWhy you need it
An algorithm is a precise list of steps for solving a problem. Every program is built from algorithms, and a good one can be the difference between a million steps and twenty.
This is where you start to think like a programmer: not only does it work? but also how many steps does it take?
The intuition
A recipe, directions to a friend's house, the steps to tie a shoelace: these are all algorithms. A good algorithm is
- precise: every step is clear, with no guessing ("add some salt" isn't precise; "add 2 g of salt" is),
- finite: it always finishes,
- correct: it gives the right answer every time.
Two algorithms for the guessing game
One by one. Guess 1, then 2, then 3… It always works, but if the number is 100 you need 100 guesses.
Split it in half. Guess the middle, 50. If your friend says "higher", the number is between 51 and 100: one question threw away half of the possibilities. Guess the middle of what's left, 75, and again, and again. Each guess halves what remains: 100 → 50 → 25 → 13 → 7 → 4 → 2 → 1. That's at most 7 guesses for any number from 1 to 100.
The gap grows with the size of the problem. For a million numbers, one by one may need a million guesses; halving needs at most 20.
Halving only works because the numbers are in order, so "higher" tells you which half to keep. That's also why dictionaries and contact lists are sorted. Searching by halving is called binary search.
The two machines on the right play both strategies. Change the secret number and compare the counts.
Definition
Algorithm
An algorithm is a finite list of precise steps that solves a problem.
Binary search
Binary search finds an item in a sorted list by repeatedly checking the middle and throwing away the half that cannot contain it.
Examples
One by one
Try it yourselfThe simple way. Try a secret of 5, then 100.
secret = 73 # change me 改这里
guesses = 0
for guess in range(1, 101):
guesses = guesses + 1
if guess == secret:
break
print("Found", secret, "after", guesses, "guesses")- L1The number your friend picked.
secret = 73 - L3Guess 1, 2, 3 … up to 100.
guess = 1 - L4Count every guess.
guesses = 1 - L5Is this the number? Not until 73.
guess = 73 - L773 guesses for 73.
Found 73 after 73 guesses
Split it in half
Try it yourselfEvery guess is the middle of the numbers that are still possible. Try 1, 100 and 50: it never takes more than 7.
secret = 73 # change me 改这里
low = 1
high = 100
guesses = 0
while low <= high:
guess = (low + high) // 2
guesses = guesses + 1
if guess == secret:
print(guess, "-> got it!")
break
elif guess < secret:
print(guess, "-> higher")
low = guess + 1
else:
print(guess, "-> lower")
high = guess - 1
print("Guesses:", guesses)- L2At first anything from 1 to 100 is possible.
low = 1, high = 100 - L6Guess the middle, rounding down.
guess = 50 - L1250 is too small: the secret is higher.
50 -> higher - L13Throw away 1 to 50.
low = 51 - L6The middle of 51 to 100.
guess = 75 - L1675 is too big: throw away 75 to 100.
high = 74 - L9A few halvings later it lands on 73.
73 -> got it! - L176 guesses instead of 73.
Guesses: 6
When the problem grows
Try it yourselfFor each size, the worst case of both strategies. Ten times more numbers costs one by one ten times more guesses, but halving only about 3 more.
for size in [100, 1000, 10000, 100000, 1000000]:
steps = 0
left = size
while left > 0:
left = left // 2
steps = steps + 1
print(size, "numbers: one by one up to", size, "| halving at most", steps)- L1Try bigger and bigger ranges.
size = 100 - L5Halve until nothing is left, counting each halving.
100, 50, 25, 12, 6, 3, 1 - L7100 numbers: at most 7 guesses.
100 … halving at most 7 - L7A million numbers: at most 20.
1000000 … halving at most 20
Common mistakes
Halving needs order
If the numbers or names are jumbled, the middle tells you nothing about which half to keep. Then going one by one is the only safe way.
"It works" isn't the whole story
Both strategies always find the number. The difference is how many steps they take, and that matters hugely when the problem is big.
Steps must be precise
"Guess somewhere around the middle" is not an algorithm step. "Guess (low + high) ÷ 2, rounded down" is. A computer needs the precise version.
Quick quiz
1. The number is from 1 to 100. You guess 50 and hear "lower". Which numbers are still possible?
Show the answer
Answer: A
"Lower" means the secret is smaller than 50, so only 1 to 49 are left. Half the numbers are gone after one guess.
2. Which of these can you search by halving?
Show the answer
Answer: B
Only the dictionary is in order. Open it in the middle and you know which half your word is in.
3. Halving, at most how many guesses for a number from 1 to 1,000?
Show the answer
Answer: A
1000 → 500 → 250 → 125 → 63 → 32 → 16 → 8 → 4 → 2 → 1: about 10 halvings.
Key points
- An algorithm is a precise, finite list of steps that solves a problem.
- Different algorithms for the same problem can need very different numbers of steps.
- Binary search halves the possibilities with each step, but only works on sorted data.
Practice
3 short exercises: think it through, change something and see what happens, then do one yourself. Answers are checked the moment you submit.
- ThinkThe next guess
The number is from 1 to 100. You guessed 50 and heard "higher". Then you guessed 75 and heard "lower".
With the halving strategy (the middle, rounded down), what is your next guess?
- ChangeA bigger range
Your friend now picks from 1 to 1000, and the secret is 999. The machine still only searches 1 to 100, so it never finds it: press Run and see.
Change the range so the machine finds 999. Keep the secret as it is.
- Your turnCount the guesses
Play halving on the numbers 1 to 16: always guess the middle, rounded down. The secret is 16.
How many guesses until you hit it? Work it out on paper first, then check with the halving machine on the right (change
secretandhigh).
Practise this lesson
Open the interactive lesson to edit and run these examples and solve the exercises with instant feedback. Free to start, no sign-up.
Interactive lessons open in order. If you have not done the earlier ones yet, you start at the course map.
Terms in this lesson
| Term | Chinese | Definition |
|---|---|---|
| Algorithm | 算法 | A finite list of precise steps that solves a problem. |
| Linear search | 顺序查找 | Checking items one by one from the start until you find the one you want. |
| Binary search | 二分查找 | Finding an item in a sorted list by checking the middle and keeping only the half that can contain it. |
| Sorted | 有序 | Arranged in order, such as smallest to largest or A to Z. |