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 3232 elements, then an incorrect guess cuts it down to have at most 1616. Binary search halves the size of the reasonable portion upon every incorrect guess.

If we start with an array of length 88, then incorrect guesses reduce the size of the reasonable portion to 44, then 22, and then 11. Once the reasonable portion contains just one element, no further guesses occur; the guess for the 1-element portion is either correct or incorrect, and we’re done. So with an array of length 8, binary search needs at most four guesses.

What do you think would happen with an array of 16 elements? If you said that the first guess would eliminate at least 8 elements, so that at most 8 remain, you’re getting the picture. So with 16 elements, we need at most five guesses.

By now, you’re probably seeing the pattern. Every time we double the size of the array, we need at most one more guess. Suppose we need at most mm guesses for an array of length nn. Then, for an array of length 2n2n, the first guess cuts the reasonable portion of the array down to size nn, and at most mm guesses finish up, giving us a total of at most m+1m+1 guesses.

Let’s look at the general case of an array of length nn. We can express the number of guesses, in the worst case, as “the number of times we can repeatedly halve, starting at nn, until we get the value 11, plus one.” But that’s inconvenient to write out. Fortunately, there’s a mathematical function that means the same thing as the number of times we repeatedly halve, starting at nn, until we get the value 11: the base-2 logarithm of nn. We write it as lgn\lg n. (You can learn more about logarithms here)

Here’s a table showing the base-2 logarithms of various values of nn:

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy