The catalog keeps growing: 8 stars, then 16, then 32, then 64.
"Linear search gets twice as slow each time it doubles," Rocket says. "What about binary search?"
Raven makes a table on her wrist computer. "What do you notice when we count the worst case for each size?"
The numbers appear: 4, 5, 6, 7. Rocket gasps. "It only goes up by one!"
Nova sparkles. "Here is a hint. Think about what one extra check does to a list."
This program counts checks for every possible target, including missing ones. Then it keeps the biggest count. max() gives the bigger of two values.
def checks_needed(items, target):
low = 0
high = len(items) - 1
checks = 0
while low <= high:
mid = (low + high) // 2
checks = checks + 1
if items[mid] == target:
return checks
elif items[mid] < target:
low = mid + 1
else:
high = mid - 1
return checks
for size in [8, 16, 32, 64]:
items = list(range(size))
worst = 0
for target in range(-1, size + 1):
worst = max(worst, checks_needed(items, target))
print(size, worst) Output: 8 4 16 5 32 6 64 7
Each check cuts the list in half. So one extra check can handle a list twice as big.
That is why doubling the list adds only one check in the worst case.
| Items | Linear search worst case | Binary search worst case |
|---|---|---|
| 8 | 8 | 4 |
| 16 | 16 | 5 |
| 32 | 32 | 6 |
| 64 | 64 | 7 |
| Statement | True or false? |
|---|---|
| Doubling the list doubles the binary search worst case. | ? |
| Doubling the list doubles the linear search worst case. | ? |
| For 64 items, binary search needs at most 7 checks. | ? |
def count_checks(items, target):
low = 0
high = len(items) - 1
checks = 0
while low <= high:
mid = (low + high) // 2
checks = checks + 1
if items[mid] == target:
return checks
elif items[mid] < target:
low = mid + 1
else:
high = mid - 1
return checks
items = list(range(16))
print(count_checks(items, 7))
print(count_checks(items, 0))
print(count_checks(items, 15)) | Statement | True or false? |
|---|---|
| count_checks(items, 7) finds 7 on the first check. | ? |
| Binary search on 16 items can need 16 checks. | ? |
| Different targets can take different numbers of checks. | ? |
| Linear search on 16 items can need 16 checks. | ? |
Amazing! You measured how two algorithms grow. Tomorrow we find the one thing binary search must have.