did you know a million items can take just twenty checks?

in a sorted list of a million entries, binary search can find a target, or establish that it is absent, in at most twenty midpoint checks. the trick is refusing to inspect entries one by one.

look at the middle entry. if the target is smaller, discard everything above it; if larger, discard everything below it. sorting makes each comparison informative about an entire half of the list.

a million possibilities become about 500,000, then 250,000, then 125,000. after ten halvings, only about a thousand remain. ten more finish the job.

this is the same strategy as guessing a number when someone reliably answers higher or lower. a guess in the middle keeps the worst-case remaining interval as small as possible.

two raised to the twentieth power is 1,048,576. twenty binary decisions can distinguish more than a million possibilities. a standard midpoint search on one million sorted entries needs no more than twenty comparisons.

2²⁰ = 1,048,576; search work grows roughly as log₂(n)

• the entries must be sorted according to the comparison you use. sorting an unsorted collection is separate work.
• the speed advantage also assumes you can jump cheaply to the middle. walking a linked list to reach that entry changes the cost.