A new batch of star IDs arrives. Rocket drops them straight into binary search and looks for 36.
The answer comes back -1. "But 36 is right there!" Rocket says. "My search is broken!"
Raven reads the list. "What do you notice about the order of these numbers?"
"They are all jumbled up," says Rocket. "30, 3, 21, 8."
Nova hovers over the list. "Here is a hint. Binary search trusts the order. What if the order is wrong?"
def binary_search(items, target):
low = 0
high = len(items) - 1
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
jumbled = [30, 3, 21, 8, 36, 12, 27, 15]
print(binary_search(jumbled, 36)) Output: -1
The middle item is 8. 36 is bigger, so the search throws away the left half. Then it checks 12, then 27, then 15.
It never looks at spot 4, where 36 sits. On a jumbled list, the thrown away half might hold the target.
| Statement | True or false? |
|---|---|
| Binary search works on any list. | ? |
| Linear search works on a jumbled list. | ? |
| Binary search throws away half the list after each check. | ? |
| On a sorted list of 64 items, binary search can take 64 checks. | ? |
def binary_search(items, target):
low = 0
high = len(items) - 1
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
jumbled = [9, 2, 7, 4, 5]
in_order = [2, 4, 5, 7, 9]
print(binary_search(jumbled, 2))
print(binary_search(in_order, 2))
print(2 in jumbled) | Statement | True or false? |
|---|---|
| in_order is sorted from smallest to biggest. | ? |
| jumbled is sorted. | ? |
| Binary search found 2 in in_order. | ? |
| in works on a jumbled list. | ? |
Week 7 complete! You found a search that is fast on big sorted lists. But how do lists get sorted? Next week we sort by hand.