The fleet's supply list will grow to hundreds of items. Rocket wants searching to stay quick.
"Linear search would check them one by one," he says. "We can do better."
Raven points to week 7 in her notebook. "What do you notice that binary search needs?"
"A sorted list!" Rocket says. "And sorted(inventory) gives us the names in order."
Nova sparkles. "Here is a hint. Check the middle, then keep the half that could hold the target."
# Part 4: find an item fast
def find_item(names, target):
low = 0
high = len(names) - 1
while low <= high:
mid = (low + high) ____ 2
if names[mid] == target:
return mid
elif names[mid] < target:
low = ____
else:
high = mid - 1
return -1
inventory = {
"water": 40,
"seeds": 12,
"lamps": 3,
"maps": 7,
"rope": 2,
"tools": 15,
}
def find_item(names, target):
low = 0
high = len(names) - 1
while low <= high:
mid = (low + high) // 2
if names[mid] == target:
return mid
elif names[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
names = sorted(inventory)
print(names)
print(find_item(names, "seeds"))
print(find_item(names, "tea")) Output: ['lamps', 'maps', 'rope', 'seeds', 'tools', 'water'] 3 -1
def find_item(names, target):
low = 0
high = len(names) - 1
while low <= high:
mid = (low + high) // 2
if names[mid] == target:
return mid
elif names[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
names = ["fuel", "maps", "rope", "tape", "wire"]
print(find_item(names, "fuel"))
print(find_item(names, "wire"))
print(find_item(names, "glue")) | Statement | True or false? |
|---|---|
| names is sorted A to Z. | ? |
| find_item returns the name it found. | ? |
| Searching for glue ends when low passes high. | ? |
| find_item is the same code as week 7. | ? |
Part 4 is in! Tomorrow we count the crew with recursion and add more supplies.