Pointer Walk

Binary Search

A million items in twenty checks, and the overflow bug that hid in the textbook version for years.

AlgorithmsBeginner8 min read

Guess the number

I am thinking of a number between 1 and 100. After each guess I say "higher" or "lower". What do you guess first?

Almost everyone says 50. Not because 50 is likely to be right, but because whichever answer comes back, half of the possibilities are gone. Then 25 or 75, and half are gone again.

That is binary search. It works on anything sorted, and it is astonishingly fast.

How it works

  1. Keep track of the range that could still hold the target

    Two markers, lo and hi. At first they cover everything.

  2. Look at the middle item

    One comparison.

  3. If it is the target, stop

    Found.

  4. If it is too small, throw away the left half. If too big, the right half

    Because the items are sorted, the target cannot be on that side.

  5. Repeat until found, or until the range is empty

    An empty range means the target is not there.

Pick a target and step through it. Greyed-out items have been ruled out.

Binary search for 41Interactive
Target
1lo, hi = 0, len(items) - 1
2while lo <= hi:
3 mid = (lo + hi) // 2
4 if items[mid] == target:
5 return mid
6 if items[mid] < target:
7 lo = mid + 1
8 else:
9 hi = mid - 1
10return -1

Variables

nothing yet

Start. Press play, or step through one line at a time.

Why it is so fast

Each check halves what is left. Going the other way: each extra check lets you search twice as many items.

ItemsChecks needed, at most
104
1,00010
1,000,00020
1,000,000,00030

A thousand times more data costs ten more checks. Checking items one by one would need a million checks for a million items. This growth is written O(log n).

The bug in the textbook version

For decades, the standard way to compute the middle was:

java
int mid = (lo + hi) / 2;

It looks harmless, and it was in widely used libraries for years before anyone noticed the problem. With a large enough array, lo + hi is bigger than the largest number an int can hold. It overflows and wraps around to a negative number.

The midpoint bug, with 32-bit integersInteractive
1int lo = 1_500_000_000;
2int hi = 2_000_000_000;
3int mid = (lo + hi) / 2; // the bug
4int safe = lo + (hi - lo) / 2; // the fix

Variables

nothing yet

Start. An int holds values up to 2,147,483,647. Watch what happens to lo + hi in a very large array.

The fix computes the same value without ever forming the large sum:

java
int mid = lo + (hi - lo) / 2;

hi - lo is the size of the range, which always fits. Languages whose integers grow as needed, such as Python, do not have this problem.

Off-by-one, the other classic

Most broken binary searches are wrong by one somewhere. The version in the animation follows three rules that go together:

  • hi starts at the last valid position, len(items) - 1.
  • The loop runs while lo <= hi, so a range of one item is still checked.
  • The middle is always excluded when narrowing: lo = mid + 1 or hi = mid - 1. Otherwise the range can stop shrinking and the loop never ends.
python
def binary_search(items, target):
    lo, hi = 0, len(items) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if items[mid] == target:
            return mid
        if items[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

More than finding a value

The same halving idea answers any question of the form "where does the answer switch from no to yes?".

  • Where should this value be inserted to keep the list sorted?
  • Which commit introduced the bug? (git bisect does exactly this.)
  • What is the smallest server size that passes the load test?

Key takeaways

  • Binary search checks the middle of a sorted range and throws away the half that cannot contain the target.
  • Each check halves the range: a million items in 20 checks, a billion in 30.
  • It only works on sorted data.
  • Compute the middle as lo + (hi - lo) / 2 to avoid overflow in languages with fixed-size integers.
  • Always exclude the middle when narrowing, or the loop may never end.

Your progress

Check your progress

0%

  1. Read the page50% of this page

    When you have gone through the page and its animations, tick it off.

  2. Take the quiz50% of this page

    7 questions, from easy to hard. Take it as often as you like: the questions change, and only your best score counts.

Saved on this device only. See all your progress