Mission Control asks a big question: how long could a catalog search ever take?
"It depends where the star is," Rocket says. "Sometimes it is quick."
Raven nods. "What do you notice about the luckiest search and the unluckiest one?"
"Luckiest is the first spot. Unluckiest is the last spot, or not there at all," Rocket says.
Nova sparkles. "Here is a hint. Engineers give those two searches special names."
The best case is the input that takes the fewest steps. For linear search, the target is in the first spot. That takes 1 check.
The worst case is the input that takes the most steps. The target is last, or missing. That takes one check per item.
| Items in the list | Best case checks | Worst case checks |
|---|---|---|
| 8 | 1 | 8 |
| 100 | 1 | 100 |
| 1,000 | 1 | 1,000 |
Look at the worst case column. When the list doubles in size, the worst case doubles too. Linear search grows at the same speed as the list.
| Statement | True or false? |
|---|---|
| The best case for linear search is always 1 check. | ? |
| Searching a longer list can never take more checks. | ? |
| A missing target is a worst case. | ? |
def checks_needed(items, target):
checks = 0
for item in items:
checks = checks + 1
if item == target:
return checks
return checks
nums = list(range(1, 101))
print(checks_needed(nums, 1))
print(checks_needed(nums, 100))
print(checks_needed(nums, 500)) | Statement | True or false? |
|---|---|
| checks_needed(nums, 500) checks every number. | ? |
| The best case depends on how long the list is. | ? |
| The worst case for 100 items is 100 checks. | ? |
| A target in the middle takes about half the worst case. | ? |
Super thinking! Next week we meet a search with a much smaller worst case. Tomorrow we search the catalog's star records.