# 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

If we start with an array of length

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

Let’s look at the general case of an array of length **base-2 logarithm** of

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

Create a free account to access the full course.

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