Binary Search Example (Classic log n algorithm)

Binary search finds a target in a sorted array by repeatedly halving the search space. You start with $n$ elements, check the middle, and discard half.

After one comparison, you have at most $\frac{n}{2}$ elements left. After two, at most $\frac{n}{4}$. After $k$ comparisons, at most $\frac{n}{2^k}$ elements remain.

You stop when the range has $1$ element, so $k = \log_2(n)$. That's why binary search runs in $O(\log n)$ time.