Binary Search — Algorithmics

Suppose you are looking for a name in a phone book. You do not start at the first page. You open somewhere near the middle, see whether you have gone too far, and throw away the half you no longer need.

The only thing binary search asks of you is that the data be sorted. Given that, every comparison halves the number of candidates still in play.

Why halving is fast

A thousand elements become five hundred, then two hundred and fifty, then one hundred and twenty-five. The number of comparisons needed is the number of times you can halve $n$ before reaching one:

T(n) = T\left(\frac{n}{2}\right) + O(1) = O(\log_2 n)

For a thousand elements that is ten comparisons. For a million, twenty. The graph is so flat that doubling your data costs you exactly one extra step.

Reading that is one thing; watching the window collapse is another. Pick a target and step through it — including a value that isn’t in the array, which is the case the formula above quietly covers.

Target 55

Step 1 / 4

Height 4 — which is exactly the worst-case comparison count.

37 is too low, so it and everything to its left is ruled out — 5 candidates remain.

Comparisons

1 5 37 − 55 = −18 too low [6, 10] · 5 left

Only the sign is read. Negative sends the search right, positive sends it left, zero means you are standing on the answer — which is why the magnitudes never matter and the window halves regardless of them.

11 elements, so never more than 4 comparisons. Try a value that isn't in the array.

The invariant

The loop is three lines, and all three exist to preserve one statement:

If the target is in the array at all, it lies within [low, high].

function binarySearch(values: readonly number[], target: number): number {
  let low = 0;
  let high = values.length - 1;

  while (low <= high) {
    const mid = Math.floor((low + high) / 2);

    if (values[mid] === target) return mid;
    if (values[mid]! < target) low = mid + 1;
    else high = mid - 1;
  }

  return -1;
}

Nothing outside the window can be the answer, because the array is sorted and we have already compared against the boundaries. When the window closes to nothing — low > high — the target was never there.

The bug everyone writes once

Math.floor((low + high) / 2) overflows in languages with fixed-width integers once low + high exceeds the maximum. The fix is to compute the offset rather than the sum:

const mid = Math.floor((low + high) / 2);
const mid = low + Math.floor((high - low) / 2);

JavaScript numbers are doubles, so this cannot bite you here until array indices exceed $2^{53}$ — which they will not. It bites in Java, C, Go, and Rust, and it sat undetected in the JDK for nine years.