Average Case of Binary Search

To simplify the argument, assume the length of the list is one less than a power of two. If not, expand the list and the following will be just a little bit on the high side.

So, let n = 2k–1. A little thought will convince you that the worst possible binary search in this case takes k steps. Also, the number of numbers that are found on pass 1 through the list is 1, on pass 2 is 2, ... on pass i is 2i–1. Thus, the average number of steps taken by a binary search to find a number in the list is:

We could use Calculus to make this easier, but, since Calculus is not a prerequisite for this course, we first remember that . [This is easily seen by writing n in binary.]

The sum needed to compute the average can be rewritten as

This can be reordered by taking out one of the 1 + 2 + 4 + 8 + ... and then one of the 2 + 4 + 8 ... as

To see that this is the same as the original, add by columns.

The first row of the above sum adds to 2k–1. In the second row, we can factor out a 2, and what is left adds to 2k–1–1, so the second row adds to 2(2k–1–1). In the succeeding rows, higher powers of 2 can be factored out leaving sums that add to one less than a power of 2. Putting all the row sums together and simplifying gives

Dividing by n to get the average gives .

Notice that for large n, this is about k–1. Thus, the average case is only about one step better than the worst case.

Finally, in terms of log(n) we could write .


Calculus-based Derivation

Let so that

Since adding zero does not change the sum, as long as we avoid x = 0.

Let . We now have .

From chapter 1,

This gives

Thus,

This is the same value derived above without using calculus.