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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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$.

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

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.