Binary Search

Think of a number between 1 and 100. I will find it in seven guesses, and you only have to tell me “higher” or “lower”.

Fifty. Higher? Seventy-five. Lower? Sixty-two. Each answer eliminates half of what is left, and halving 100 seven times gets you to one.

That is binary search. You already know it; the article is about writing it without introducing a bug.

The obvious way

Look at everything until you find it:

for (let i = 0; i < values.length; i++) {
  if (values[i] === target) return i;
}

A million items, a million comparisons. Perfectly fine — if the data has no order to exploit. When it is sorted, this loop is throwing away the only useful thing you were given.

Halving, and what it buys

Sorted means the middle element tells you which half to keep:

• Middle is too small → the answer is to its right.
• Middle is too big → the answer is to its left.
• Middle is it → done.

Step through it, and watch the ruled-out half go dashed:

Each comparison discards half the remaining range, so the count is “how many times can you halve $n$ before reaching 1?” — which is exactly $\log_2 n$.

The last row is the one that lands. Going from a million to a billion — a thousand times the data — adds ten comparisons.

The code, and the two lines that go wrong

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

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

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

  return -1;
}

Every part of that is load-bearing.

low + (high - low) / 2, not (low + high) / 2

They are the same number, and one of them overflowed.

Java’s Arrays.binarySearch shipped with (low + high) / 2 for nine years. On arrays over a billion elements the sum exceeded Integer.MAX_VALUE, wrapped negative, and the search crashed. Joshua Bloch wrote it, Jon Bentley wrote the book it came from, and it survived every review.

JavaScript numbers are 64-bit floats so you will not hit this — but write the safe form anyway. It costs nothing, and it is the version that survives being ported to a language where it matters.

What actually makes it correct

One sentence, true before the loop and after every iteration:

If the target is in the array, it is somewhere between low and high inclusive.

Check it. Before the loop, the range is the whole array — true. Each iteration discards only a side that has been shown not to contain the target — still true. When low passes high, the range is empty, and the sentence says the target was never there.

The version you should actually write

Finding an exact match is the least useful variant. What you usually want is the boundary — the first position where something becomes true:

/** First index where predicate(values[i]) is true. values.length if never. */
function lowerBound(values: readonly number[], predicate: (v: number) => boolean): number {
  let low = 0;
  let high = values.length;      // ← one PAST the end, deliberately

  while (low < high) {           // ← and now < is correct
    const mid = low + Math.floor((high - low) / 2);
    if (predicate(values[mid]!)) high = mid;    // mid might be the answer — keep it
    else low = mid + 1;                         // mid is definitely not — drop it
  }

  return low;                    // low === high, and that is the boundary
}

The conventions changed together and that is not accidental: high is now an exclusive bound, so the empty range is low === high and the loop is <. Mix the two styles — exclusive bound with <= — and you index one past the end.

This one function answers all of these:

lowerBound(values, (v) => v >= target);       // first element ≥ target
lowerBound(values, (v) => v > target);        // first element > target
lowerBound(values, (v) => v >= target) - 1;   // last element < target

Insertion points, ranges, counts — all boundaries. Learn this version rather than the exact-match one and you will write fewer bugs.

It is not really about arrays

Binary search works on any monotone predicate: something false, then true, with no flip-flopping. The array is incidental.

// "What is the smallest capacity that finishes the job in time?"
let [low, high] = [1, 1_000_000_000];
while (low < high) {
  const mid = low + Math.floor((high - low) / 2);
  if (canFinishInTime(mid)) high = mid;
  else low = mid + 1;
}

There is no array anywhere. This is “binary search on the answer”, and it is one of the highest-leverage techniques there is: if a problem asks for a minimum or maximum, and checking a specific value is easy, you can search the answer space in $O(\log(\text{range}))$ checks.