Binary Search

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.

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.