Comet copies fifteen of Beacon's sorted water readings onto cards and lines them up along the bench.
"Fifteen cards," she says. "Linear search could take fifteen checks. How many does binary search take?"
Wren picks up a pencil. "Let's investigate. We will count every check."
Nova projects a small number above each card: 1, 2, 3, all the way to 15. "These are the indexes," she says.
"The list starts at index 1," Wren reminds them, "just like in Beacon's pseudocode."
Comet taps card 8. "This one is in the middle. Let's go."
Here are the fifteen readings as a Beacon list. The values are sorted from smallest to largest.
waterLog ← [12, 18, 23, 31, 37, 42, 48, 55, 61, 66, 70, 74, 81, 88, 95] index: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Binary search keeps track of two indexes. Low is the first index still in play. High is the last.
The middle index is low plus high, divided by 2. When that falls between two indexes, the crew rounds down.
At the start, low is 1 and high is 15. So the first middle index is 8.
| Check | Low | High | Middle index | Value there | What happens |
|---|---|---|---|---|---|
| 1 | 1 | 15 | 8 | 55 | 55 is less than 74, so keep indexes 9 to 15 |
| 2 | 9 | 15 | 12 | 74 | Found it |
Binary search found 74 in 2 checks. Linear search would have checked indexes 1 through 12: 12 checks.
Binary search is often more efficient, not always. A value near the start of a list can be quicker to find by linear search.
Efficiency is an estimate of how much computing an algorithm uses. It is usually written in terms of the size of the input.
You can measure efficiency informally by counting how many times a statement, or a group of statements, runs.
Different correct algorithms for the same problem can have different efficiencies. Both searches are correct, but they are not equally fast.
The table shows the most checks each search could need, using the crew's round-down rule.
| Sorted list size | Linear search, most checks | Binary search, most checks |
|---|---|---|
| 8 | 8 | 4 |
| 16 | 16 | 5 |
| 32 | 32 | 6 |
| 64 | 64 | 7 |
| 128 | 128 | 8 |
| Statement | True or false? |
|---|---|
| Binary search always takes fewer checks than linear search. | ? |
| Two correct algorithms for the same problem can have different efficiencies. | ? |
| For linear search, the most checks grows at the same rate as the list. | ? |
| On the AP reference sheet, the first index of a list is 0. | ? |
Nice tracing. Tomorrow's Beacon Lab turns binary search into a card game.