Step by step
The example above, written out — the same steps the animation plays.
- 1Find 12. 7 sorted values. Look in the middle, then discard the half that can't hold 12.
- 2Middle is 7. mid = (0 + 6) / 2 = 3. Is 7 equal to 12?
- 3Discard the left half. 7 < 12, so 12 can only be to the right. 7 → 3 left to search.
- 4Middle is 12. mid = (4 + 6) / 2 = 5. Is 12 equal to 12?
- 5Found 12. Found 12 at index 5 after 2 checks — not 7.
What's happening?
- LOW and HIGH mark the part of the list that could still hold the target; MID is halfway between them.
- If the middle value is too small, everything to its left is too small as well — the whole left half is discarded.
- The search space halves every step: 1,000 values need about 10 checks, a million about 20.
Complexity
- Time
- O(log n)
- Space
- O(1) iterative
Where you'll meet it
Database indexes, Git bisect, finding a word in a dictionary, autocomplete over sorted lists, and "binary search on the answer" in interview problems.
Common mistake
Using it on unsorted data, or writing low < high instead of low ≤ high and missing the last element.
FAQ
Why is binary search O(log n)?
Each check halves what is left. Halving n until one item remains takes about log₂ n steps.
Does binary search need sorted data?
Yes. Discarding a half is only safe because everything on one side is known to be smaller or larger.
How many checks for a million items?
At most 20, because 2²⁰ is just over a million.