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* = 2^{k}–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 2^{i–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
2^{k}–1.
In the second row, we can factor out a 2, and what is left adds to
2^{k–1}–1,
so the second row adds to
2(2^{k–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
.

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.