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.

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.