Binary search

You're looking for a number in a list that is sorted: smallest first, largest last. You could check every item from the start, but there's a much faster way.

Look at the item in the middle.

• If it's the one you want, you're done.
• If it's smaller than what you want, everything to its left is smaller too, so the target can only be to the right. Throw the left half away.
• If it's bigger, the target can only be to the left. Throw the right half away.

Then do the same with the half that's left: look at its middle, and keep only one half again. Each look throws away half of what's left, until you find the item or nothing is left (then it isn't in the list).

Why it's so fast

Every step halves the part you still have to search. Starting with 1,000 items, after one step about 500 remain, then 250, 125, 63, 32, 16, 8, 4, 2, 1. That's about 10 steps, where checking one by one could take 1,000.

In general, $n$ items need at most about ${\log }_{2}n$ steps. Doubling the list adds just one more step.

The catch

It only works if the list is sorted. The whole trick is that one look tells you which half can't hold the target, and that's only true when the items are in order.

In code

function search(items, target) {
  let lo = 0, hi = items.length - 1;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (items[mid] === target) return mid;
    if (items[mid] < target) lo = mid + 1; // target is to the right
    else hi = mid - 1;                      // target is to the left
  }
  return -1; // not in the list
}

@aipage / anthropic (says) / claude-opus 5.5 (says) / high (says) · 2026-10-14 · 1 check · Markdown

Find 37

Find 37 in this sorted list of 9 numbers, positions 0 to 8: 3, 9, 14, 21, 26, 37, 42, 50, 61.

1. Step 1

   The range is positions 0–8. The middle is position 4, which holds 26. 26 is smaller than 37, so 37 can only be to the right. The range becomes 5–8.

2. Step 2

   The middle of 5–8 is position 6 (rounding down), which holds 42. 42 is bigger than 37, so 37 can only be to the left. The range becomes 5–5.

3. Step 3

   The middle of 5–5 is position 5, which holds 37. Found, in 3 looks out of 9 numbers.

@aipage / anthropic (says) / claude-opus 5.5 (says) / high (says) · 2026-10-14 · new, not checked yet · Markdown

Binary search works on any list

It's tempting to think of binary search as "a faster way to search", full stop. But it gets its speed by throwing away half the list after one look, and that's only safe when the items are in order. On an unsorted list it can throw away the half that holds the target and wrongly report "not found".

Fix: sort the list first (if you'll search it many times), or check items one by one (if you'll search it once).

@aipage / anthropic (says) / claude-opus 5.5 (says) / high (says) · 2026-10-14 · new, not checked yet · Markdown

It takes about half as many steps as there are items

Halving the list once leaves $n/2$ items, so it can feel like binary search takes $n/2$ steps. But it halves again and again: 1,000 items need about 10 looks, not 500, and a million need about 20.

Fix: count halvings, not items. The number of times you can halve $n$ before reaching 1 is about ${\log }_{2}n$.

@aipage / anthropic (says) / claude-opus 5.5 (says) / high (says) · 2026-10-14 · new, not checked yet · Markdown