Binary search, one step at a time

Think of a number between 1 and 100. If I guess 50 and you say it is higher, I can stop considering every number below 51. I can do the same thing again with the remaining range.

That is the idea behind binary search. Try the game first, then step through the code to see how it keeps track of what is left.

Guess the number

I'm thinking of a number between 1 and 100. If you choose the middle each time, how many guesses are enough in the worst case?

Slide and guess. The shaded region shows where the number can be. Try to find it in seven guesses.

1255075100

Choose a guess and see which numbers remain possible.

Choosing the middle removes roughly half the remaining possibilities each time. Seven guesses are enough for any number from 1 to 100. Try the automatic player and watch the range shrink.

Follow the code

The code searches a sorted list of 15 numbers. lo and hi mark the remaining range. mid is the index in the middle.

At each step, the code compares the target with the middle value. If they differ, it removes the half that cannot contain the target. Pick a number and watch the highlighted line.

Step through binary search

The shelf holds 15 numbers. Worst case, how many midpoint checks before the loop ends?

Choose a target from the list or tap a bar, then press Step to follow the code.

Target 42

ready

lo mid hi

lo	…
hi	…
mid	…
arr[mid]	…
target	42
midpoint checks	0
still possible	15 books

Pick a target, press step. The interpreter will tell you what it's looking at.

Moving lo to mid + 1 removes the middle value and everything below it. Moving hi does the reverse. This list needs at most four midpoint checks. For the missing target, the loop ends when lo passes hi.

The midpoint uses Math.floor to round down. JavaScript bit shifts convert numbers to 32-bit integers, which is an unnecessary limit here.

Try a much larger list

Halving makes the number of checks grow slowly. Doubling the list adds at most one more midpoint check. A sorted list of a billion items needs no more than 30.

The comparison below assumes each check takes one second so the difference is easy to see. It is not a timing benchmark.

Compare the number of checks

How many midpoint checks are enough for a billion sorted items?

Change the list size to compare the number of checks.

list size 1,000 items

check every book

halve the shelf

A linear search may need to check every item. Binary search keeps halving the remaining range. That difference becomes large as the list grows, provided the data is already sorted and supports access by index.

Both bars use the same scale within each setting. A minimum visible width keeps the smaller bar readable. Counts are worst case.

The list has to be sorted

The code can discard half the list because it knows which values are smaller or larger than the midpoint. That only works if the list is sorted.

Shuffle the numbers below. The target is still there, but the same code can now discard the part that contains it.

Search a shuffled list

The number 23 is in this list. Shuffle the list and run the search. Check whether the result is correct.

shelf SORTED

lomidhi

On this shuffled list, the search returns “not found” even though 23 is present. The code runs without an error. The result is wrong because the sorted-order assumption no longer holds.

Sorting also takes work. For a single search through an unsorted list, a linear scan may be the better choice.

What I would take from this

Compare the target with the middle value, then narrow the remaining range.
The number of midpoint checks grows logarithmically with the list size.
An empty range means the target was not found, provided the list was sorted.
Check that the data meets the algorithm's assumptions before trusting its result.

For one search through a small unsorted list, checking each item may be simpler. Sorting becomes more useful when you need to search the same data repeatedly.

About this example

The stepper computes a trace of the JavaScript shown. It counts midpoint checks, rather than individual JavaScript comparisons. The guessing game picks a random number. The shuffled example uses a fixed arrangement so the failure is repeatable. The one-second comparison shows operation counts, not measured runtime.