Binary Logarithm (Base 2)

The binary logarithm $\log_2(n)$ is the most common logarithm in computer science. It tells you how many times you can divide $n$ by $2$ before reaching $1$.

For example, $\log_2(64) = 6$. You can halve $64$ six times: $64 \to 32 \to 16 \to 8 \to 4 \to 2 \to 1$. Each division is one step, so six divisions means $\log_2(64) = 6$.

This is why binary search runs in $O(\log n)$ time. Each comparison cuts the search space in half, and you can only halve $n$ about $\log_2(n)$ times before you find your answer.