Counting the Steps in Binary Search

I opened this chapter with the claim that binary search is faster than linear search. Let’s make that precise by counting how many comparisons (target compared to array elements) each one makes. That is a good proxy for how long the search takes.

Best case and worst case

Recall from the dynamic-array chapter the best and worst case of linear search.

The best case is when the target is at the first position of the array, so we find it immediately with one comparison.
The worst case is when the target is not present in the array, so we have to check every element until we reach the end.

Now let’s consider the best and worst case of binary search.

The best case is when the target is right at the middle of the range we are looking at, so we find it with one comparison.
The worst case is when the target is not present in the array, so we keep halving the range until it becomes empty. The number of comparisons is then the number of times we can halve the range before nothing is left.

The best case of the two searches is the same: one comparison. So the best case cannot tell us much about which search to prefer. The best case also only holds when the target happens to be in the position the search checks first, so it does not tell us much about the search in general. The worst case is the more useful here because it gives us a guarantee about the maximum number of comparisons needed. It says the search will never be slower than that count, for any array and any target.

In linear search, the worst case is $n$ comparisons, where $n$ is the size of the array. In binary search, the worst case is not $n$ comparisons, but some smaller number. Let’s work out what that number is.

How the range shrinks

Start with an array of $n$ elements. The first comparison looks at the middle and discards half, leaving a range of about $n /2$ . The next comparison halves that, leaving about $n /4$ . And so on: each step cuts the range in half again.

Let’s tabulate the size of the range after each step:

Step	Range size	As a power of two
$0$	$n$	$n / 2^{0}$
$1$	$n /2$	$n / 2^{1}$
$2$	$n /4$	$n / 2^{2}$
$3$	$n /8$	$n / 2^{3}$
$⋮$	$⋮$	$⋮$
$x$	$1$	$n / 2^{x}$

The search keeps going until the range is down to a single element, because after that one more comparison empties it and we stop. After $x$ steps the range has shrunk to $1$ or $n / 2^{x}$ .

Solving for the number of steps

The range reaches $1$ when

\frac{n}{2 ^{x}} = 1

Multiply both sides by $2^{x}$ :

2^{x} = n

So $x$ is the power you must raise $2$ to in order to get $n$ . That number is the base-2 logarithm of $n$ , written $lo g_{2} n$ .

x = lo g_{2} n

If you have not worked with logarithms in a while, this is the reading you need for now: $lo g_{2} n$ is the number of times you can halve $n$ before reaching $1$ . Halve 8 and you get 4, then 2, then 1. That is three halvings, and indeed $lo g_{2} 8 = 3$ . It is also exactly the number of comparisons our trace made when we searched for $42$ in the array $\[3, 9, 14, 21, 28, 33, 42, 55\]$ of size $8$ .

First comparison:
┌────┬────┬────┬────┬────┬────┬────┬────┐
│  3 │  9 │ 14 │ 21 │ 28 │ 33 │ 42 │ 55 │
└────┴────┴────┴────┴────┴────┴────┴────┘
                  ↑
              compare to

Second comparison:
┌────┬────┬────┬────┬────┬────┬────┬────┐
│░ 3░│░ 9░│░14░│░21░│ 28 │ 33 │ 42 │ 55 │
└────┴────┴────┴────┴────┴────┴────┴────┘
                            ↑
                        compare to

Third comparison:
┌────┬────┬────┬────┬────┬────┬────┬────┐
│░ 3░│░ 9░│░14░│░21░│░28░│░33░│ 42 │ 55 │
└────┴────┴────┴────┴────┴────┴────┴────┘
                                 ↑
                            compare to

For simplicity, we can drop the base and just write $lo g n$ to mean $lo g_{2} n$ . The base is understood to be $2$ when we are talking about binary search or other algorithms that halve a range.