Comet holds up Wren's count from yesterday. "Ten checks to learn that 40 is missing? In a sorted list, I could tell after 39 and 42."
Wren nods. "What does the evidence say? If the middle number is too small, everything to its left is too small too."
"So we can throw away half the list with one check," Comet says. "And then half again."
Nova projects the ten sorted grams with three markers above them: low, mid and high. "How can I help?" she asks. "Move the markers one check at a time. Write each one down."
Wren slides the trace table across the bench. "Lead programmer, move the markers."
Binary search needs data in sorted order. It starts in the middle and removes half of the list each step, until it finds the target or nothing is left.
The names low and high mark the part of the list that could still hold the target. The midpoint is mid = (low + high) // 2. If items[mid] is too small, low moves past mid. If it is too large, high moves before mid.
# binary_trace.py
# A copy of binary_search that prints each check.
def binary_trace(items, target):
low = 0
high = len(items) - 1
while low <= high:
mid = (low + high) // 2
print("low", low, "mid", mid, "high", high, "value", items[mid])
if items[mid] == target:
return mid
elif items[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
# Made-up data from the FieldSim story: the catalog grams, sorted.
sorted_grams = [7, 12, 18, 25, 30, 39, 42, 51, 65, 88]
print("Found at", binary_trace(sorted_grams, 39))
print("Found at", binary_trace(sorted_grams, 40)) | Check | low | high | mid | items[mid] | What happens (target 39) |
|---|---|---|---|---|---|
| 1 | 0 | 9 | 4 | 30 | 30 is too small: low = 5 |
| 2 | 5 | 9 | 7 | 51 | 51 is too large: high = 6 |
| 3 | 5 | 6 | 5 | 39 | found: give back 5 |
low 0 mid 4 high 9 value 30 low 5 mid 7 high 9 value 51 low 5 mid 5 high 6 value 39 Found at 5 low 0 mid 4 high 9 value 30 low 5 mid 7 high 9 value 51 low 5 mid 5 high 6 value 39 low 6 mid 6 high 6 value 42 Found at -1
Binary search trusts that the list is sorted. Here it runs on the catalog grams in catalog order, which are not sorted. Made-up data from the FieldSim story.
# unsorted.py
from field_data import CATALOG
from search import binary_search, linear_search
grams = []
for label, kind, g in CATALOG:
grams.append(g)
print(grams)
print(binary_search(grams, 39))
print(linear_search(grams, 39)) [42, 18, 65, 7, 30, 51, 12, 88, 25, 39] -1 9
Comet made exactly that change once. Here is what a search for 100 does with high = len(items).
# binary_oops.py
def binary_oops(items, target):
low = 0
high = len(items)
while low <= high:
mid = (low + high) // 2
if items[mid] == target:
return mid
elif items[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
sorted_grams = [7, 12, 18, 25, 30, 39, 42, 51, 65, 88]
print(binary_oops(sorted_grams, 100)) Traceback (most recent call last):
File "binary_oops.py", line 19, in <module>
print(binary_oops(sorted_grams, 100))
~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^
File "binary_oops.py", line 9, in binary_oops
if items[mid] == target:
~~~~~^^^^^
IndexError: list index out of range | Statement | True or false? |
|---|---|
| Binary search needs the data in sorted order. | ? |
| Each check of binary search removes about half of what is left. | ? |
| On an unsorted list, binary search always finds the target anyway. | ? |
| mid is worked out as (low + high) // 2. | ? |
Three checks instead of six, four instead of ten. Tomorrow you count the work on a list of a thousand items.