Binary Search

Binary search finds a value in a sorted list by checking the middle element and discarding the half that cannot contain it, again and again.

Find 12

Looking for 12

1
3
5
7
9
12
15
LOW
HIGH

7values left · at most ⌈log₂(7+1)⌉ = 3 checks

  • Middle (checked)
  • Ruled out
  • Found

7 sorted values. Look in the middle, then discard the half that can't hold 12.

Step 1 / 5
Checks
0
Still possible
7
low = 0, high = n − 1
while low ≤ high:
mid = (low + high) / 2
if a[mid] == target: found
else if a[mid] < target: low = mid + 1
else: high = mid − 1
not found

Numbers are sorted and de-duplicated for you — binary search only works on sorted data.

Step by step

The example above, written out — the same steps the animation plays.

  1. 1Find 12. 7 sorted values. Look in the middle, then discard the half that can't hold 12.
  2. 2Middle is 7. mid = (0 + 6) / 2 = 3. Is 7 equal to 12?
  3. 3Discard the left half. 7 < 12, so 12 can only be to the right. 7 → 3 left to search.
  4. 4Middle is 12. mid = (4 + 6) / 2 = 5. Is 12 equal to 12?
  5. 5Found 12. Found 12 at index 5 after 2 checks — not 7.

What's happening?

  1. LOW and HIGH mark the part of the list that could still hold the target; MID is halfway between them.
  2. If the middle value is too small, everything to its left is too small as well — the whole left half is discarded.
  3. 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.