I'm a little bit confused about the analysis of binary search. In almost every paper, the writer assumes that the array size $n$ is always $2^k$. Well I truly understand that the time complexity becomes $\log(n)$ (worst case) under this assumption. But what if $n \neq 2^k$?

For example if $n=24$, then we have 5 iterations for 24
4 i. for 12
3 i. for 6
2 i. for 3
1 i. for 1

So how do we get the result $k=\log n$ in this example (I mean of course every similar example whereby $n\neq2^k$)?

  • 3
    $\begingroup$ Ceiling function? $\endgroup$ Nov 3, 2012 at 10:20
  • $\begingroup$ I think you're right. $\endgroup$
    – Hasan Tahsin
    Nov 3, 2012 at 20:20
  • $\begingroup$ How can you show then that $\lceil \log n \rceil = O(\log n)$? $\endgroup$
    – Hasan Tahsin
    Nov 3, 2012 at 20:28
  • 1
    $\begingroup$ $\lceil \log n \rceil \leq \log(n) + 1 \leq 2\log(n)$ for $n \geq 2$, q.e.d. $\endgroup$
    – Raphael
    Nov 4, 2012 at 15:34

1 Answer 1


$n=2^k$ is a simplifying assumption that ensures binary search "goes through" properly. If the array has a length that is not a power of two, you have to break ties when choosing middle elements, "halves" are not equally large and not all decisions lead to the same number of steps.

The worst-case number of steps on an array of size $n$ can certainly bounded from above by the maximum number of steps on an array of size $2^k$, $n \leq 2^k$. If we choose $k$ as small as possible, we obtain $k = \lceil \log n \rceil$.

With $\lceil \log n \rceil \leq \log(n) + 1$ we see that the worst-case number of steps is indeed asymptotically equal to $\log n$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.