Comet is convinced. "Binary search wins. Let's use it for everything."
Wren holds up two fingers. "What does the evidence say? On ten items it saved a few checks. I want to see a bigger list before I vote."
"And it needs sorted data," Wren adds. "Our catalog is not sorted yet."
Nova projects two columns of tally marks, one short and one very long. "How can I help?" she asks. "Count the work. Then judge each search by how fast it is, whether it is right, and how clear it is."
Comet picks up a pencil. "Lead programmer, let's count."
Binary search is typically faster than linear search. A count shows how much faster on our lists.
count_both.py has copies of both searches that count checks. It tries four targets on the sorted grams, then one target on a list of 1,000 numbers. Made-up data from the FieldSim story.
# count_both.py
# Copies of both searches that count their checks.
def linear_count(items, target):
checks = 0
for i in range(len(items)):
checks += 1
if items[i] == target:
return checks
return checks
def binary_count(items, target):
checks = 0
low = 0
high = len(items) - 1
while low <= high:
mid = (low + high) // 2
checks += 1
if items[mid] == target:
return checks
elif items[mid] < target:
low = mid + 1
else:
high = mid - 1
return checks
# Made-up data from the FieldSim story: the catalog grams, sorted.
sorted_grams = [7, 12, 18, 25, 30, 39, 42, 51, 65, 88]
for target in [7, 39, 40, 88]:
print(target, linear_count(sorted_grams, target), binary_count(sorted_grams, target))
big = list(range(0, 2000, 2))
print(len(big), "items")
print(1998, linear_count(big, 1998), binary_count(big, 1998)) 7 1 3 39 6 3 40 10 4 88 10 4 1000 items 1998 1000 10
| Target | Linear checks | Binary checks |
|---|---|---|
| 7 (first item) | 1 | 3 |
| 39 | 6 | 3 |
| 40 (missing) | 10 | 4 |
| 88 (last item) | 10 | 4 |
| 1998 in 1,000 items | 1000 | 10 |
Efficiency: on the long list, binary search did 10 checks where linear search did 1,000.
Correctness: binary search gave a wrong answer on the unsorted grams yesterday. Linear search was right on both lists.
Clarity: linear search is shorter and easier to check by eye. Binary search has three markers to keep straight.
| Claim | True or false? |
|---|---|
| Binary search is the better choice for every list. | ? |
| Linear search is correct on unsorted data. | ? |
| On the 1,000-item list, binary search used far fewer checks. | ? |
| Linear search can beat binary search when the target is the first item. | ? |
Trace these on paper first, with low, mid and high. Use the sorted grams: 7, 12, 18, 25, 30, 39, 42, 51, 65, 88.
# search_drill.py from search import binary_search sorted_grams = [7, 12, 18, 25, 30, 39, 42, 51, 65, 88] print(binary_search(sorted_grams, 12)) print(binary_search(sorted_grams, 65))
1 8
Wren writes tests for search.py. The edge cases are a missing target, the first item and the last item.
# test_search.py
# Tests for search.py. Run this file: it prints one line when all pass.
from field_data import FIELD
from sample import Sample
from search import binary_search, find_in_grid, find_label, linear_search
def test_linear():
assert linear_search([42, 18, 65], 65) == 2
assert linear_search([42, 18, 65], 40) == -1
assert find_label([Sample("S01", "basalt", 42)], "S02") is None
assert find_in_grid(FIELD, "#") == (0, 5)
def test_binary():
nums = [7, 12, 18, 25, 30, 39, 42, 51, 65, 88]
assert binary_search(nums, 7) == 0
assert binary_search(nums, 88) == 9
assert binary_search(nums, 40) == -1
test_linear()
test_binary()
print("All search tests passed") All search tests passed
You counted the work instead of guessing. Tomorrow you play the halving game with your family.