Section 3.3 Analysis of Algorithms
209
Let C(n) stand for the maximum number of comparisons required to do a
binary search on an n-element list. Then Ca
n
2
b stands for the maximum number
of comparisons required to search a list half that size. If we are to keep cutting the
list in half, it is convenient to consider only the case where we get an integer value
each time we cut in half, so we will assume that n = 2
m
for some m ≥ 0.The recurrence relation for C(n) is
C(1) = 1
(1 comparison to search a
1- element list)
C(n) = 1 + C a
n
2
b for n ≥ 2, n = 2
m
(1 comparison against the middle
element, then however many
comparisons are required for half
the list)
This recurrence relation was solved in the previous section (Examples 24 and 25).
The solution is
C(n) = 1 + log n
By the preceding example, the maximum number of comparisons required
to do a binary search on an n-element ordered list, with n = 2
m
, is 1 + log n.
In Example 14, n was 8, and four comparisons (1 + log 8) were required in the
worst case (x not in the list). A sequential search would require eight comparisons.
Because
1 + log n < n for n = 2
m
, n ≥ 4
binary search is almost always more efficient than sequential search. However,
the sequential search algorithm does have one big advantage—if the list being
searched is unsorted, the sequential search algorithm works, but the binary search
algorithm does not. If we first sort the list and then use the binary search algorithm, we must then consider the work involved in sorting the list. Exercises 13–34
at the end of this section ask you to count the operations required to sort a list by
several different algorithms.
■
Practice 16
Fill in the following table for the worst-case number of comparisons required for
sequential search and binary search on a list of the indicated size.
n
Sequential Search
binary Search
64
1024
32768
Although we have computed the work for binary search only on a list of size n
where n is a power of 2, this gives us a range for the work required for values of n