Describe the time complexity of the binary search algorithm in terms of number of comparisons?
For simplicity, assume there are $n = 2^k$ elements in the list $a_1, a_2, . . . , a_n$, where $k$ is a nonnegative integer.
Question 1: Without writing the whole proof, I would like to clarify the first step of this proof. At the first stage the search is restricted to a list with $2^{k−1}$ terms. So far, two comparisons have been used. At the second stage, the search is restricted to a list with $2^{k−2}$ terms, etc. Can you please explain how each time the lest is restricted by subtracting from $k$ the number $1$?
Question 2: why the whole search requires the ceiling of $log$: $2\left\lceil \log(n)\right\rceil + 2$. One comparison to exist the loop and another to check if the value is $x$ or the key plus $2\left\lceil \log(n)\right\rceil$ whole comparisons before existing the loop.
About Question 1. Lets say we play a game called: I guess any number between 0 and 1024 in just 10 questions (so our list starts with 1024 possible solutions).
My first question is: Is this number larger than 512?
Regardless of your answer, I effectively reduce the amount of possible solutions to 512 (either larger than 512, or smaller or equal to 512). As such, I have halved the list of numbers the solution is in. If I repeat this procedure (so I ask, is it larger than 256), I half the list again. If your list starts at size $2^k$, then the half of that list equals $0.5 \cdot 2^k = 2^{-1} \cdot 2^k = 2^{k-1}$.
Regarding question 2: Suppose the requested solution is larger than the list (to use the example above, the solution would be 1024). This would mean that the answer to each question is simply "yes". At the final iteration, the guessed value will be $512+256+128+64+32+16+8+4+2+1 = 1023$. Hereby, it is obvious that it does not equal the solution, as such the binary search algorithm includes this additional question that checks if the solution is inside the search range. This check can be performed before the while loop to save iterations, but that is not done here.