Proof Details

By definition we have

$$2^{\log_2{n}} = n.$$ Further, as $2^x$ is increasing in $x\ge 0$ (this can be shown e.g. by noting that the derivative of $2^x$ is positive for $x\ge 0$), we have that for any $x\ge \log_2(n+1)$, we have $$2^x > n \text{ or equivalently } \frac{n}{2^x} < 1.$$ The proof is complete by noting that $\left\lceil \log_2(n+1)\right\rceil$ is the smallest integer greater than or equal to $\log_2(n+1)$.

Binary Search

                                        //Input: A[0],...,A[n-1];v (A is sorted)
 
					left=0;
					right=n-1;
 
					while(left <= right)
					{
						mid=ceil( (right+left)/2);
						if(A[mid]==v)
							return mid; // v is present 
						else if(A[mid]< v)
							left=mid+1; // Search for v in right half
						else
							right = mid-1; // Search for v in left half
					}
 
					return -1; // v is not present
				

Proof Details

We first note that all steps outside of the while loop take $O(1)$ time. Further, each iteration also takes $O(1)$ time (since each step in the iteration are basic operations such as comparison, assignment and simple arithmetic operations). Thus, if we can argue that while loop runs $O(\log_2{n})$ times, we would be done.

To bound the number of iterations of the while loop, let $\ell_i$ and $r_i$ denote the value of left and right at the start of the $i$th iteration. Further, we keep track of $p_i=r_i-\ell_i$. Note that $p_0=n-1$ and for the smallest integer $x$ such that $p_x\lt 1$, the algorithm will terminate at the end of the $x$th iteration. This is because at the start of this round left<=right but then if line 10 is not executed then either line 13 or 15 will ensure that at the start of the next iteration left> right and hence the algorithm will stop. (Note that if line 10 is executed then the algorithm will also terminate.)

Finally we argue that $x=O(\log_2{n})$. Towards this end consider the $i$th iteration for some $i\le \left\lceil \log_2{n}\right\rceil$. Then either line 10 is executed (in which case the algorithm terminates and we are done) otherwise either line 13 or 15 are executed. In the latter case we claim that

$$p_{i+1}\le \frac{p_i}{2}.$$ To see this note that if line 13 is executed then $r_{i+1}=r_i$ and $\ell_{i+1} \ge \frac{\ell_i+r_i}{2}+1$ and if line 15 is executed then $\ell_{i+1}=\ell_i$ and $r_{i+1}\le \frac{\ell_i+r_i}{2}$. It can then be verified that in both cases $p_{i+1}\le p_i/2$. Finally, we note that this implies¹ that $$p_i\le \frac{p_0}{2^i}=\frac{n-1}{2^i}.$$ Lemma 1 and the observation above that $p_x\lt 1$ then implies $x=O(\log_2{n})$, as desired.

Modified Binary Search

                                        //Input: A[0],...,A[n-1];v (A is sorted)
 
                                        left=0;
                                        right=n-1;
 
                                        while(left <= right)
                                        {
                                                mid=ceil( (right+left)/c); // Note that c has replaced 2
                                                if(A[mid]==v)
                                                        return mid; 
                                                else if(A[mid]< v)
                                                        left=mid+1; 
                                                else
                                                        right = mid-1; 
                                        }
 
                                        return -1; // v is not present