Binary search, visualized

The idea

Binary search finds a value in a sorted array by repeatedly halving the range it still has to look at. Each comparison throws away half of what is left, so even a billion values need at most 30 comparisons.

Try it below. Pick a value and press Search, or walk through it one comparison at a time with Step. Generate a new sorted array whenever you like.

Search for a value

-+Search

Step through

Step

New sorted array

Shuffle

 

Reset

Pick a target and press Search. 15 sorted values, at most 4 comparisons.

If the animation is too fast or too slow, change the speed for every visualization on this page:

Change the animation speed

50%75%100%150%200%

How each step works

Keep two indexes, lo and hi, around the part of the array that might still contain the target. Then repeat:

1. Look at the middle element, the mid.
2. If it equals the target, you are done, and the cell turns green.
3. If it is smaller than the target, everything to its left is smaller too, so move lo past it.
4. If it is larger, move hi before it.

When lo passes hi, the value is not in the array.

static int binarySearch(int[] values, int target) {
    int lo = 0, hi = values.length - 1;
    while (lo <= hi) {
        int mid = (lo + hi) >>> 1; // unsigned shift avoids int overflow
        if (values[mid] == target) return mid;
        if (values[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

Why databases care

values	worst-case comparisons
1,000	10
1,000,000	20
1,000,000,000	30

A B-tree index applies the same halving idea inside every node, and adds a very wide fan-out so the tree stays only a few levels deep on disk. That is the next article in this series.