Guess my number
I think of a number from 1 to 100. You guess. I only say "higher" or "lower".
Would you guess 1, then 2, then 3? No. You would guess 50. If I say "higher", you would guess 75. Each guess throws away a big part of the numbers. Computers search this way too.
Key words
| Word | What it means | Example |
|---|---|---|
| Algorithm | A set of steps to solve a problem. | |
| Linear search | Look at each item in turn, from the start, until you find it. | |
| Binary search | Look at the middle item and throw away the half that cannot hold the target. Repeat. | |
| Target | The value you are looking for. | |
| Sorted | In order, such as smallest to largest or A to Z. | |
| Index | The position of an item in a list. The first is 0. | |
| Comparison | Checking one value against another. | is it equal to the target? |
| Best case | The situation where the algorithm does the least work. | |
| Worst case | The situation where the algorithm does the most work. |
The cells students fill in are left blank in this preview.
Linear search: one by one
In a linear search you start at the first item. Is it the target? If not, go to the next. Keep going until you find it or reach the end.
It is simple. It works on any list, sorted or not.
Try it: linear search
names = ["Mei", "Tom", "Aisha", "Sam", "Zara"]
target = "Sam"
position = 0
checks = 0
found_at = -1
while position < len(names) and found_at == -1:
checks = checks + 1
if names[position] == target:
found_at = position
position = position + 1
print("Found at index", found_at, "after", checks, "checks")
# Try the target "Mei" and then "Bob". How many checks each time?
Trace table: linear search for Sam
| Check | Index | Item | Is it Sam? |
|---|---|---|---|
| 1 | 0 | Mei | No |
| 2 | 1 | Tom | No |
| 3 | 2 | Aisha | No |
| 4 | 3 | Sam | Yes: found at index 3 |
The cells students fill in are left blank in this preview.
Quick check: linear search
Have a go
Quick check: linear search
3 questionsYour answers are marked here and are not kept. A college account keeps every student’s marks.
Binary search: halve the list
Binary search needs a sorted list. Look at the middle item. Is it the target? Then stop.
If the target is smaller, the answer can only be in the lower half. Throw away the upper half. If the target is larger, do the opposite. Repeat with what is left.
Worked example: binary search, found
| Step | Search area (index) | Middle | Item in the middle | Decision |
|---|---|---|---|---|
| 1 | 0 to 6 | 3 | 15 | 15 is smaller than 27: use the upper part, 4 to 6 |
| 2 | 4 to 6 | 5 | 27 | It is 27: found at index 5 |
The cells students fill in are left blank in this preview.
Try it: binary search
numbers = [3, 8, 12, 15, 21, 27, 40]
target = 27
low = 0
high = len(numbers) - 1
checks = 0
found_at = -1
while low <= high and found_at == -1:
middle = (low + high) // 2
checks = checks + 1
if numbers[middle] == target:
found_at = middle
elif numbers[middle] < target:
low = middle + 1
else:
high = middle - 1
print("Found at index", found_at, "after", checks, "checks")
# // divides and drops the decimal part. Try the target 10.