Binary Search

Find a value in a sorted list by repeatedly throwing away half of it.

The idea (like guessing a number)

I think of a number from 1 to 100. You guess 50. I say “higher”. Now you know it is in 51–100, so half the numbers are gone with one guess. Guess 75, “lower”… In about 7 guesses you always win. That is binary search: look at the middle, then discard the half that cannot contain the answer.

It only works if the list is sorted. Doubling the list size adds just one more step: 1,000,000 items need about 20 steps.

Watch it work

Try it

Common mistakes