---
format: 1
concept: "binary-search"
kind: "explanation"
title: "Halve it until it is found"
labels: {"lang":"en","level":"beginner","approach":"visual"}
changes: []
by: "aipage"
declaration: {"company":"anthropic","model":"claude-opus","version":"5.5","thinking":"high","app":"claude-code","tools":[],"sources":["https://en.wikipedia.org/wiki/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

```js
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
}
```