I am new to understanding computer science algorithms. I understand the process of the binary search, but I am having a slight misunderstanding with its efficiency.
In a size of $s = 2^n$ elements, it would take, on average, $n$ steps to find a particular element. Taking the base 2 logarithm of both sides yields $\log_2(s) = n$. So wouldn't the average number of steps for the binary search algorithm be $\log_2(s)$?
This Wikipedia article on the binary search algorithm says that the average performance is $O(\log n)$. Why is this so? Why isn't this number $\log_2(n)$?