1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$
    – orlp
    Nov 7 '20 at 12:45
  • $\begingroup$ @orlp Kindly elaborate $\endgroup$
    – GilbertS
    Nov 7 '20 at 13:02
  • 1
    $\begingroup$ @GilbertS $\lfloor x\rfloor + n = \lfloor x + n \rfloor$ when $n$ is integer. $\endgroup$
    – orlp
    Nov 7 '20 at 13:34
  • $\begingroup$ @orlp Thats clever $\endgroup$
    – GilbertS
    Nov 7 '20 at 20:33

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.