Where is invoice 4460?
A customer rings about invoice 4460. Your system holds thousands of invoices.
You could read them one at a time from the top. If the invoices are in number order, there is a much quicker way.
This lesson shows both ways, and when you can use each.
By the end of this lesson
Note
I can find an item by linear search and by binary search.
Key words
| Word | What it means |
|---|---|
| Algorithm | steps that solve a problem |
| Search | to find where an item is |
| Linear search | checking each item in turn from the start |
| Sorted | in order, smallest to largest or A to Z |
| Binary search | checking the middle of a sorted list and throwing half away |
| Step | one check of one item |
The cells students fill in are left blank in this preview.
Linear search checks each item in turn
A linear search starts at the first item. It checks it, then the next, then the next.
It stops when it finds the item, or when the list runs out. It works on any list, sorted or not.
In the worst case it checks every item. A list of 1,000 can take 1,000 steps.
Try it: a linear search
# Invoice numbers, in the order they arrived.
invoices = [4410, 4402, 4498, 4415, 4460, 4433]
wanted = 4460
steps = 0
found_at = -1
for index in range(len(invoices)):
steps = steps + 1
if invoices[index] == wanted:
found_at = index
break
print("Found at index", found_at, "after", steps, "steps")
# Change wanted to 9999, a number that is not there, then press Run.
Binary search halves a sorted list
Binary search only works on a sorted list. It checks the item in the middle.
If that is the item, it stops. If the item it wants is bigger, it throws away the left half. If smaller, it throws away the right half.
Then it checks the middle of what is left, again and again.
Worked example: finding 45 in 15 orders
| Step | Part still searched | Middle item | Decision |
|---|---|---|---|
| 1 | index 0 to 14 | 37 at index 7 | 45 is bigger: keep the right half |
| 2 | index 8 to 14 | 58 at index 11 | 45 is smaller: keep the left half |
| 3 | index 8 to 10 | 41 at index 9 | 45 is bigger: keep the right half |
| 4 | index 10 to 10 | 45 at index 10 | Found it |
The cells students fill in are left blank in this preview.
Try it: a binary search
# Order numbers, sorted from smallest to largest.
orders = [3, 8, 12, 17, 21, 26, 30, 37, 41, 45, 52, 58, 63, 70, 77]
wanted = 45
low = 0
high = len(orders) - 1
steps = 0
while low <= high:
steps = steps + 1
middle = (low + high) // 2
print("Step", steps, "checks index", middle, "which holds", orders[middle])
if orders[middle] == wanted:
print("Found at index", middle)
break
elif orders[middle] < wanted:
low = middle + 1 # throw away the left half
else:
high = middle - 1 # throw away the right half
# Change wanted to 3, then to 77, and press Run each time.
A common mistake
Warning
Many people think binary search works on any list. It works only when the list is sorted. On an unsorted list it throws away the half that holds the item and reports it missing. So sort first, or use a linear search.
Worked example: most steps needed
| Items | Linear search | Binary search |
|---|---|---|
| 15 | 15 | 4 |
| 1,000 | 1,000 | 10 |
| 1,000,000 | 1,000,000 | 20 |
The cells students fill in are left blank in this preview.