Running Time of Binary Search

We know that linear search on an array of nn elements might have to make as many as nn guesses. You probably already have an intuitive idea that binary search makes fewer guesses than linear search. You even might have perceived that the difference between the worst-case number of guesses for linear search and the binary search becomes more striking as the array length increases. Let’s see how to analyze the maximum number of guesses that a binary search makes.

The key idea is that when binary search makes an incorrect guess, the portion of the array that contains reasonable guesses is reduced by at least half. If the reasonable portion had $32$ elements, then an incorrect guess cuts it down to have at most $16$. Binary search halves the size of the reasonable portion upon every incorrect guess.

If we start with an array of length $8$, then incorrect guesses reduce the size of the reasonable portion to $4$, then $2$, and then ...