170
Recursion, Recurrence Relations, and Analysis of Algorithms
This algorithm searches the section of list L between L[i] and L[j] for item x;
initially i and j have the values 1 and n, respectively. The first clause of the major if
statement is the basis step that says x cannot be found in an empty list, one where
the first index exceeds the last index. In the major else clause, the midpoint item in
a section of the list must be found. (If the section contains an odd number of items,
there is indeed a midpoint item; if the section contains an even number of items,
it is sufficient to take as the “midpoint” item the one at the end of the first half of
the list section.) Comparing x with the midpoint item either locates x or indicates
which half of the list to search next, the half before the midpoint or the half after
the midpoint.
example 14
Let’s apply the binary search algorithm to the list
3, 7, 8, 10, 14, 18, 22, 34
where the target item x is the number 25. The initial list is not empty, so the midpoint item is located and determined to have the value 10. Then x is compared with
the midpoint item. Because x > 10, the search is invoked on the second half of the
list, namely, the items
14, 18, 22, 34
Again, this list is nonempty, and the midpoint item is 18. Because x > 18, the
second half of this list is searched, namely, the items
22, 34
In this nonempty list, the midpoint item is 22. Because x > 22, the search continues
on the second half of the list, namely,
34
This is a one-element list, with the midpoint item being the only item. Because
x < 34, a search is begun on the “first half” of the list; but the first half is empty.
The algorithm terminates at this point with the information that x is not in the list.
This execution requires four comparisons in all; x is compared, in turn, to 10,
18, 22, and 34.
PRaCtiCe 10 In a binary search of the list in Example 14, name the elements against which x is
compared if x has the value 8.
■
We have now seen a number of recursive definitions. Table 3.1 summarizes
their features.
Recursion, Recurrence Relations, and Analysis of Algorithms
This algorithm searches the section of list L between L[i] and L[j] for item x;
initially i and j have the values 1 and n, respectively. The first clause of the major if
statement is the basis step that says x cannot be found in an empty list, one where
the first index exceeds the last index. In the major else clause, the midpoint item in
a section of the list must be found. (If the section contains an odd number of items,
there is indeed a midpoint item; if the section contains an even number of items,
it is sufficient to take as the “midpoint” item the one at the end of the first half of
the list section.) Comparing x with the midpoint item either locates x or indicates
which half of the list to search next, the half before the midpoint or the half after
the midpoint.
example 14
Let’s apply the binary search algorithm to the list
3, 7, 8, 10, 14, 18, 22, 34
where the target item x is the number 25. The initial list is not empty, so the midpoint item is located and determined to have the value 10. Then x is compared with
the midpoint item. Because x > 10, the search is invoked on the second half of the
list, namely, the items
14, 18, 22, 34
Again, this list is nonempty, and the midpoint item is 18. Because x > 18, the
second half of this list is searched, namely, the items
22, 34
In this nonempty list, the midpoint item is 22. Because x > 22, the search continues
on the second half of the list, namely,
34
This is a one-element list, with the midpoint item being the only item. Because
x < 34, a search is begun on the “first half” of the list; but the first half is empty.
The algorithm terminates at this point with the information that x is not in the list.
This execution requires four comparisons in all; x is compared, in turn, to 10,
18, 22, and 34.
PRaCtiCe 10 In a binary search of the list in Example 14, name the elements against which x is
compared if x has the value 8.
■
We have now seen a number of recursive definitions. Table 3.1 summarizes
their features.