Finding one order among a million
A search algorithm finds one item in a collection, and the two classic ones are linear search and binary search. Knowing both lets you choose the one that stays fast when the data grows from a thousand rows to a million.
A web shop looks up an order number every time a customer asks where their parcel is. One method reads every order. The other reads about twenty.
By the end of this lesson
Note
I can compare linear search and binary search by the steps they take.
Key words
| Word | What it means | Example |
|---|---|---|
| Linear search | look at each item in turn until you find it | |
| Binary search | halve a sorted list again and again | |
| Sorted | in order, smallest first | 2, 5, 8, 12 |
| Index | the position of an item, counting from 0 | |
| Middle | the item halfway between low and high | |
| Worst case | the input that needs the most steps |
The cells students fill in are left blank in this preview.
Linear search checks every item in turn
Linear search starts at the first item and compares each one with the target until it finds it or runs out.
It works on any list, sorted or not. In the worst case the target is last or missing, and the search takes n steps. That is linear growth.
Run a linear search and count
# Linear search: look at the items one by one.
orders = [31, 12, 47, 8, 25, 60, 3, 19]
target = 60
steps = 0
position = -1
for i in range(len(orders)):
steps = steps + 1
if orders[i] == target:
position = i
break
print("found at", position, "after", steps, "steps")
# Change target to 31, then to 99, and run again.
A line-by-line search in the terminal
The command grep is a linear search over lines. With -n it prints the line number, and with -m1 it stops at the first match.
The Run below writes a million numbers and searches for 750000. The number before the colon is the line where grep stopped, so grep read that many lines.
Search a million lines
seq 1 1000000 | grep -n -m1 '^750000$'Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Binary search halves a sorted list
Binary search compares the target with the middle item. If the target is bigger, the lower half cannot hold it, so you throw that half away. If smaller, you throw away the upper half.
Then you repeat on what is left. Each step halves the list, so 1000 items need at most 10 steps.
Worked example: find 23 in ten items
| Step | Low | High | Middle item | What happens |
|---|---|---|---|---|
| 1 | 0 | 9 | 16 | 16 is smaller than 23, so low moves to 5 |
| 2 | 5 | 9 | 56 | 56 is bigger than 23, so high moves to 6 |
| 3 | 5 | 6 | 23 | Found at index 5 |
The cells students fill in are left blank in this preview.
Run a binary search and count
# Binary search: the list must be sorted.
items = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target = 23
low = 0
high = len(items) - 1
steps = 0
position = -1
while low <= high:
middle = (low + high) // 2
steps = steps + 1
if items[middle] == target:
position = middle
break
if items[middle] < target:
low = middle + 1
else:
high = middle - 1
print("found at", position, "after", steps, "steps")
# Change target to 91, then to 40, and run again.
A million items need about twenty steps
Doubling the list adds only one step, because one more halving covers it. So the steps grow like the number of times you can halve n. That is logarithmic growth.
Python's bisect_left is a ready-made binary search. The Runs below ask it for a position and count the halvings of a million.
Binary search a million numbers
python3 -c "import bisect; print(bisect.bisect_left(range(1, 1000001), 750000))"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Halvings needed for a million
python3 -c "import math; print(math.ceil(math.log2(1000000)))"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Binary search only works on a sorted list
The method relies on the order. When it throws half the list away, it assumes the target cannot be there.
On an unsorted list that assumption is false, and the search can miss an item that is present. Run the example, then check which method suits which job.
See binary search miss an item
# The same method on a list that is NOT sorted.
items = [9, 2, 7, 4, 5]
target = 2
low = 0
high = len(items) - 1
position = -1
while low <= high:
middle = (low + high) // 2
if items[middle] == target:
position = middle
break
if items[middle] < target:
low = middle + 1
else:
high = middle - 1
print("2 is really at position 1, the search says", position)
Sort three numbers first
printf '3\n1\n2\n' | sort -nShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
A common mistake
Warning
Many people think binary search is always the faster choice. It is only correct on a sorted list, and sorting costs steps too. For one search on an unsorted list, linear search is the right tool. Use binary search when you search the same sorted data many times.