Proof of worst-case time complexity of Binary Search

Question

I know that using the Master Theorem, one can easily arrive at the worst-case time complexity. However, how would I go about proving that it is in $O(lg(n))$ by defining upper and lower bounds? I have already proven that it is a non-decreasing function. And know that the equation can be represented by $T(n) = lg(n) + c$.

Answer 1

Note that $$\lg(n)+c=O(\lg(n))$$

Answer 2

Assume

$$2^m\le n<2^{m+1}.$$

After successive steps of division, we will have

$$2^{m-1}\le n'<2^{m},$$

then

$$2^{m-2}\le n''<2^{m-1},$$

and so on, until

$$2^0\le n^{(m)}<2^1.$$

Every split takes one comparison* and at worst we will be performing $m+1$ comparisons (*or two if we also test for equality).

Hence,

$$T(n)\le\lfloor \log_2n\rfloor+1.$$