Objective
Search a sorted array by repeatedly halving the search window and watch how few probes it takes compared with a linear scan.
The idea
Start with a target in a sorted list. Binary search cuts the remaining space in half on every probe - find out exactly why it needs so few guesses.
Try this
- 1Search for a value at the very start and at the very end.
- 2Probe a value that is not in the list and see where it stops.
- 3Count probes for an array twice as large - it barely grows.
- 4Compare with linear search on the same data.
Watch for
- Each probe halves the search interval.
- log2(n) probes cover an array of size n.
- The midpoint check tells you which half to discard.
- Without a sorted array the whole trick collapses.