# Binary Search, Explained Step by Step

> Check the middle of a sorted array and throw away the half that can’t hold the key.

Searching algorithm. Interactive version, with a step-by-step visualizer of a real recorded run: https://www.tmread.me/algorithms/binary-search

## Complexity

| | Big-O | Why |
|---|---|---|
| Best time | O(1) | The key is right in the middle. |
| Average time | O(log n) | Each check halves what’s left. |
| Worst time | O(log n) | A million values take at most 20 checks. |
| Extra space | O(1) | Two pointers, no recursion. |

## What is binary search?

Binary search finds a value, the key, in a sorted list by halving the list again and again. It checks the middle value. If that is the key, done. If the key is bigger, the whole left half can be thrown away, because every value there is even smaller. If the key is smaller, throw away the right half. Then do the same thing with what is left.

It is the “guess a number between 1 and 100” game played perfectly. Guess 50. “Higher.” Guess 75. “Lower.” Each guess cuts the options in half, so you never need more than 7 guesses.

The one rule: the list must be sorted. Without that, throwing half away is not safe.

## How it works, step by step

Press play above. `lo` and `hi` mark the part of the list that can still hold the key. Everything outside them fades out. The blue bar is the middle value being compared with the key. Green means found.

1. Set `lo = 0` and `hi` to the last index.
2. While `lo <= hi`, find the middle: `mid = (lo + hi) // 2`.
3. If `a[mid]` equals the key, return `mid`.
4. If `a[mid]` is smaller than the key, the key can only be on the right: `lo = mid + 1`.
5. Otherwise it can only be on the left: `hi = mid - 1`.
6. If `lo` passes `hi`, nothing is left. Return −1.

Switch to the “absent” preset to see the ending: `lo` and `hi` close in on each other, cross, and the search stops without a match.

## Time and space complexity

Each step halves the range. Starting from `n` values, after `k` steps about `n / 2^k` are left. The search ends when that reaches 1, so it takes about `log₂ n` steps.

That grows very slowly. 1,000 values take at most 10 checks. A million take 20. A billion take 30.

Best case, O(1): the key is exactly in the middle. Average and worst case, O(log n).

Space is O(1) for this loop version. A recursive version uses O(log n) space for the call stack, which is why the loop is usually preferred.

## Common mistakes

Binary search is short, but famously easy to get wrong. Watch for these:

- Using `lo < hi` with `hi = n - 1`. It skips the last candidate. With inclusive bounds, the loop condition is `lo <= hi`.
- Setting `lo = mid` or `hi = mid` instead of `mid + 1` / `mid - 1`. The range can stop shrinking and loop forever.
- Overflow in `(lo + hi) / 2`. In languages with fixed-size integers (Java, C, Go on huge arrays), `lo + hi` can overflow. Use `lo + (hi - lo) / 2`. Python’s integers don’t overflow.
- Searching an unsorted list. It won’t crash; it will just give wrong answers.

## When to use it

Any time you search sorted data more than once. Sort once in O(n log n), then every search is O(log n).

Binary search is also a way of thinking, not just a search. You can use it to find the first value that passes a test, the square root of a number, or the first bad commit in a history (that is what `git bisect` does).

Most languages ship it: Python’s `bisect` module, Go’s `slices.BinarySearch` and `sort.Search`, and Java’s `Arrays.binarySearch`. JavaScript has no built-in, so it is worth knowing how to write one.

## Code

### Python

```python
def binary_search(a, key):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == key:
            return mid
        if a[mid] < key:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1
```

### TypeScript

```ts
function binarySearch(a: number[], key: number) {
  let lo = 0, hi = a.length - 1;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (a[mid] === key) {
      return mid;
    }
    if (a[mid] < key) {
      lo = mid + 1;
    } else {
      hi = mid - 1;
    }
  }
  return -1;
}
```

### Go

```go
func binarySearch(a []int, key int) int {
    lo, hi := 0, len(a)-1
    for lo <= hi {
        mid := (lo + hi) / 2
        if a[mid] == key {
            return mid
        }
        if a[mid] < key {
            lo = mid + 1
        } else {
            hi = mid - 1
        }
    }
    return -1
}
```

## Questions

### Why does binary search need a sorted list?

Throwing away half the list is only safe if every value on that side is known to be too small or too big. Sorting guarantees that.

### How many steps does binary search take?

At most about `log₂ n` + 1. For a million values, that is 20.

### Is ternary search faster than binary search?

No. It takes fewer rounds, but each round makes two comparisons, so it ends up making more comparisons overall.

## Related algorithms

- [Ternary Search](https://www.tmread.me/algorithms/ternary-search.md): Split a sorted array into thirds with two midpoints and keep one third.
- [Exponential Search](https://www.tmread.me/algorithms/exponential-search.md): Double a bound until it passes the key, then binary search that range.
- [Interpolation Search](https://www.tmread.me/algorithms/interpolation-search.md): Guess where the key should be from its value, like opening a dictionary near the right letter.

---

From The Missing README (computer science, made visible). Want to run your own code and watch every step? Join Cohort 0, the early-access group: https://www.tmread.me/#cohort