How binary search finds anything in 4 guesses

Fifteen sorted numbers, and you can find any one of them by looking at four. Each guess throws away half of what is left — which is why doubling the list only costs you one more look.

Step 1 of 6

Start with everything

15 candidates

The list is sorted, which is the only thing binary search needs. Looking for 73. A linear scan would check up to 15 numbers; this will check four. The window of numbers still in play is everything.

  4  8 15 16 23 42 55 73 81 88 91 94 96 97 99
  ^-----------------window-----------------^

All 6 steps as text

1
Start with everything
The list is sorted, which is the only thing binary search needs. Looking for 73. A linear scan would check up to 15 numbers; this will check four. The window of numbers still in play is everything.
4 8 15 16 23 42 55 73 81 88 91 94 96 97 99 ^-----------------window-----------------^
2
Look at the middle, not the start
Take the midpoint of the window: position 8, holding 55. This is the whole idea. Checking the middle means that whatever the answer is, you learn which half it is in — so one comparison rules out seven numbers instead of one.
4 8 15 16 23 42 55 73 81 88 91 94 96 97 99 ^-----------------window-----------------^ ^ 55 — too low, 73 is to the right
3
Throw away the left half
73 is greater than 55, and the list is sorted, so nothing at or left of 55 can be the answer. Half the list is gone after a single look, and it will never be considered again.
73 81 88 91 94 96 97 99 ^-------window-------^
4
Repeat on what is left
Same move on the smaller window. The midpoint is 91. Too high this time, so now everything from 91 rightwards goes — including the four numbers beyond it.
73 81 88 91 94 96 97 99 ^-------window-------^ ^ 91 — too high, go left
5
Two left
The window is down to 73 and 81 from an original fifteen. Midpoint is 81, still too high, so it goes too. Notice how little work each step is: one comparison, and the problem halves again.
73 81 ^--win--^ ^ 81 — too high, go left
6
Found it, in four looks
One candidate remains, and it is 73. Four comparisons for fifteen numbers. Double the list to thirty and it costs five; a million numbers costs twenty. That is what halving each time buys you — the cost grows with the number of times you can halve the list, not with its length.
73 ^^ found

Explanation written by AI

Why sorted is the whole price of admission

Every step depends on one deduction: if the midpoint is too low, everything to its left is too low as well. That is only true because the list is sorted. Sorting costs more than a single search — so binary search pays off when you search the same list many times, which is exactly what an index is for.

The shape of the cost

Each look halves the candidates: 15, 8, 4, 2, 1. The number of steps is how many times you can halve the list before one thing is left, which is the logarithm. It is why a phone book, a dictionary and a database index all feel instant however large they get — and why the answer to 'what if it were a million numbers' is 'twenty looks'.

Check your understanding

A million sorted numbers. Roughly how many guesses does binary search need?

Pick one to check yourself.