The Art of Binary Search

I'm thinking of a number between 1 and 100. Each time you guess, I'll tell you whether my number is higher or lower. What's your first guess?

If you said 50, you already know binary search. No matter what I say, half of the possible numbers are gone in a single guess. Keep guessing the middle, and you'll find any number in at most seven tries.

That same idea lets a computer search a sorted list of a billion items in about 30 steps.

The setup#

Binary search has one requirement: the data must be sorted. Given a sorted array and a target, we want the index of the target, or to know that it isn't there.

We keep track of two positions, low and high, which mark the part of the array that could still contain the target. At the start, that's the entire array.

Halving the range#

At each step, we look at the element in the middle of the range:

• If it is the target, we're done.
• If it's smaller than the target, the target must be to its right. Everything from low to the middle can be thrown away.
• If it's bigger, the target must be to its left, so we throw away everything from the middle to high.

Pick a target and step through the search. L, M and H mark low, mid and high:

The code#

Here's that process written out in JavaScript:

function binarySearch(array, target) {  let low = 0;  let high = array.length - 1;  while (low <= high) {    const mid = Math.floor((low + high) / 2);    if (array[mid] === target) return mid;    if (array[mid] < target) low = mid + 1;    else high = mid - 1;  }  return -1;}

It's short, but almost every character matters.

Where the bugs hide#

Binary search is notorious for off-by-one errors. Here are the three most common ones:

1. Using low < high instead of low <= high. When low and high point to the same element, that element hasn't been checked yet. Stop the loop early and you'll miss targets at the edges.
2. Setting low = mid instead of low = mid + 1. We already know array[mid] isn't the target. Keeping it in the range can leave the loop stuck on the same two elements forever.
3. Overflowing on low + high. In languages with fixed-size integers, adding two large indexes can overflow. Writing low + Math.floor((high - low) / 2) avoids it. JavaScript numbers are large enough that this rarely matters, but it famously broke Java's own implementation for years.

Why it's so fast#

Each step cuts the remaining range in half. Starting with n elements, after k steps we have n / 2ᵏ left, and we stop when that reaches one. That makes binary search O(log n).

Every time the data grows a thousand times bigger, binary search needs only about ten more steps. Not bad for an algorithm you already knew as a guessing game.