The crew's catalog has grown to ten samples, and Comet wants a quick way to look one up. "Is S07 in the catalog?" Wren asks.
Comet prints the whole list and scrolls. "There it is! I just looked."
"What does the evidence say?" Wren asks. "Your eyes skipped two lines on the way down. A program should not skip any."
Nova projects the ten labels in a row, with a small light stepping from one to the next. "How can I help?" she asks. "Check each one in order. Stop when you find it, or when you run out."
Comet nods at you. "Lead programmer, write the stepping light."
Linear search checks each item in order until it finds the target, or until every item has been checked.
The function linear_search() gives back the index where it found the target. If the target is not in the list, it gives back -1 instead.
Your field_data.py from week 5 ends with CATALOG, the list of ten samples. Check that yours has these lines. Made-up data from the FieldSim story.
CATALOG = [
("S01", "basalt", 42),
("S02", "quartz", 18),
("S03", "clay", 65),
("S04", "mica", 7),
("S05", "granite", 30),
("S06", "shale", 51),
("S07", "slate", 12),
("S08", "flint", 88),
("S09", "chalk", 25),
("S10", "sandstone", 39),
] # linear_try.py
from field_data import CATALOG
def linear_search(items, target):
"""Index of the first item equal to target, or -1."""
for i in range(len(items)):
if items[i] == target:
return i
return -1
labels = []
grams = []
for label, kind, g in CATALOG:
labels.append(label)
grams.append(g)
print(linear_search(labels, "S07"))
print(linear_search(labels, "S11"))
print(linear_search(grams, 39)) 6 -1 9
find_label() is linear search over Sample objects. It compares each sample's label and gives back the whole Sample, or None when nothing matches.
# find_try.py
from field_data import CATALOG
from sample import Sample
def find_label(samples, label):
"""The Sample with this label, or None."""
for s in samples:
if s.label == label:
return s
return None
samples = []
for label, kind, grams in CATALOG:
samples.append(Sample(label, kind, grams))
found = find_label(samples, "S08")
print(found.kind, found.grams)
print(find_label(samples, "S11")) flint 88 None
# find_oops.py
from field_data import CATALOG
from sample import Sample
def find_label(samples, label):
"""The Sample with this label, or None."""
for s in samples:
if s.label == label:
return s
return None
samples = []
for label, kind, grams in CATALOG:
samples.append(Sample(label, kind, grams))
print(find_label(samples, "S11").kind) Traceback (most recent call last):
File "find_oops.py", line 17, in <module>
print(find_label(samples, "S11").kind)
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
AttributeError: 'NoneType' object has no attribute 'kind' | Statement | True or false? |
|---|---|
| Linear search only works on a sorted list. | ? |
| Linear search stops as soon as it finds the target. | ? |
| A missing target makes linear search check every item. | ? |
| -1 means the target was found at the end of the list. | ? |
You can now find any sample by checking one item at a time. Tomorrow you search the field grid the same way.