Look at the middle
The 12 cards are sorted, in order, smallest first. Look at the middle card. Is it too small? Keep the half with bigger numbers.
The range is the cards that could still be the one.
Step 1 of 5
- 12 places in range.
- Place 6 is too small. 6 left.
- Place 9 is too small. 3 left.
- Place 11 is too small. 1 left.
- Place 12: found. 4 looks.
The rule
Halving means checking the middle and dropping half. Dropping a card means you no longer look at it.
A jumbled row is not in order. A middle look on a sorted row drops about half the cards. On a jumbled row, it can drop the wrong half.
In a sorted row, every card before the middle is smaller. So a wanted card must lie after a too-small middle.
Looks in the worst case
| Cards | One by one | Halving |
|---|---|---|
| 4 | 4 | 3 |
| 16 | 16 | 5 |
| 1000 | 1000 | 10 |
The bigger the row, the more halving saves.
Halve the row. Then try the jumbled one.
Loading lab…