3
$\begingroup$

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$)?

Improve this question
$\endgroup$
  • 3
    $\begingroup$ Ceiling function? $\endgroup$ – The Unfun Cat Nov 3 '12 at 10:20
  • $\begingroup$ I think you're right. $\endgroup$ – Hasan Tahsin Nov 3 '12 at 20:20
  • $\begingroup$ How can you show then that $\lceil \log n \rceil = O(\log n)$? $\endgroup$ – Hasan Tahsin Nov 3 '12 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 '12 at 15:34
7
$\begingroup$

$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$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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