Time complexity of binary search

Question

Proposition: The binary search algorithm runs in $O(\log n)$ time for a sorted sequence with $n$ elements.

When justifying this claim, first we say that with each recursive call the number of candidate entries still to be searched is given by the value $$ high - low + 1 $$

The middle index, $mid$, is given by $$ mid = \Biggl\lfloor\frac{high + low}2\Biggr\rfloor $$

We say that the number of remaining candidates is reduced by at least one half with each recursive call. Hence the number of remaining candidates, $n$, when we shift our $high$ index to the $(mid - 1)$ index is given by:

$$ n = (mid - 1) - low + 1 $$ $$ n = \Biggl\lfloor\frac{high + low}2\Biggr\rfloor - 1 - low + 1 $$ $$ n = \Biggl\lfloor\frac{high + low}2\Biggr\rfloor - low $$ $$ n \le \Biggl\lfloor\frac{high -low + 1}2\Biggr\rfloor $$ This is the part I don't understand how did we get from the equality equation to the inequality equation?

Again, when we are computing the maximum number of recursive calls performed, $r$, we say that $r$ is the smallest integer such that

$$ \frac{n}{2^r} < 1 $$ So: $$ r > \log n $$ $$ r = \lfloor \log n \rfloor + 1 $$

Similarly, how did we get from the inequality equation to the equality equation?

Any help will be appreciated to help me understand this proof.

Answer 1

Let me start with the first question. Since $\lfloor x \rfloor \leq x$, $$ \left\lfloor \frac{\mathit{high}+\mathit{low}}{2} \right\rfloor - \mathit{low} \leq \frac{\mathit{high}+\mathit{low}}{2} - \mathit{low} \leq \frac{\mathit{high}-\mathit{low}}{2}. $$ To complete the proof, we use the inequality $\frac{x}{2} \leq \lfloor \frac{x+1}{2} \rfloor$, which holds for integer $x$. To see this, notice that for even $x = 2y$, the inequality reads $y \leq y$, and for odd $x = 2y+1$, it reads $y+1/2 \leq y+1$.

Now for the second question. We want to know what is the smallest integer $r$ such that $r > \log n$. Since $\lfloor x \rfloor > x-1$, we see that $\lfloor \log n \rfloor + 1 > (\log n - 1) + 1 = \log n$. On the other hand, since $\lfloor x \rfloor \leq x$, we see that $\lfloor \log n \rfloor \leq \log n$, and in particular, it is not the case that $\lfloor \log n \rfloor > \log n$. Therefore $\lfloor \log n \rfloor + 1$ is smallest integer $r$ such that $r > \log n$.

• orlp: The first inequality isn't even tight, since $low$ is an integer. The $+1$ is entirely unnecessary since you can just move $low$ into the floor.
• GilbertS: @orlp Kindly elaborate
• orlp: @GilbertS $\lfloor x\rfloor + n = \lfloor x + n \rfloor$ when $n$ is integer.
• GilbertS: @orlp Thats clever