Binary Search: The Guess-the-Number Game

The plain-language idea

You've probably played this game: someone picks a number between 1 and 100, and you have to guess it. After each guess, they tell you "higher" or "lower." What's your best first guess?

Most people's instinct, once they think about it, is 50 — not 1, not 99. Why? Because 50 sits exactly in the middle. If they say "higher," you've just thrown out numbers 1 through 50 in one move — half the board is gone, from a single guess. If they say "lower," you threw out 51 through 100 instead. Either way, half the possibilities vanish.

Now you guess again, right in the middle of whatever's left — say 75, if the answer was "higher" than 50. Same trick: half of what remained is gone. Guess by guess, the pile of possible numbers keeps cutting in half, until there's only one number left standing.

That's binary search. "Binary" just means "splitting into two," which is exactly what happens every time you guess the middle: the remaining possibilities split into a half you keep and a half you throw away.

See it in a real thing: guessing a number in a sorted list

Here's the same idea, done on a sorted array instead of "1 to 100" — searching for a target value by repeatedly checking the middle.

function binarySearch(sortedArr, target) {
  let low = 0;
  let high = sortedArr.length - 1;

  while (low <= high) {
    // Check the middle of what's left, not the middle of the whole array.
    const mid = Math.floor((low + high) / 2);

    if (sortedArr[mid] === target) {
      return mid; // found it
    } else if (sortedArr[mid] < target) {
      low = mid + 1; // target is bigger — throw away the lower half
    } else {
      high = mid - 1; // target is smaller — throw away the upper half
    }
  }

  return -1; // not in the array
}

console.log(binarySearch([2, 5, 8, 12, 16, 23, 38, 56, 72, 91], 23)); // 5

Trace it: low is 0, high is 9, so mid is 4 — that's 16. 16 < 23, so throw away everything at or below index 4; low becomes 5. Now mid is 7 — that's 56. 56 > 23, so throw away everything at or above index 7; high becomes 6. Now mid is 5 — that's 23. Found it, in 3 guesses, out of 10 numbers.

What people usually miss

Watch out

• Trying binary search on an unsorted list. The whole trick depends on knowing that everything to one side of the middle is smaller and everything to the other side is bigger. Without sorting, "higher" or "lower" tells you nothing about where to look next.
• Guessing linearly instead of jumping to the middle. Guessing 1, then 2, then 3 works eventually, but it throws away almost none of the remaining possibilities each time. The speed of binary search comes entirely from cutting the pile in half, not from getting lucky.
• Off-by-one mistakes with low and high. Forgetting to move low or high past the middle you already checked can make the search loop forever or skip the answer. This is a normal, extremely common bug to hit the first several times you write this — not a sign you don't understand the idea.

The genealogy: this is the phone book, made precise

This is the exact same trick as flipping to the middle of a phone book to find a name, then flipping to the middle of whichever half is left — the phone-book picture used earlier in this track to explain why some searches are fast. Binary search is that same halving instinct, written out as code so a computer can do the flipping for you, guess after guess, automatically.