Java Reference
In-Depth Information
18.25
Choosing between an iterative search and a recursive search.
Since the recursive sequential
search is tail recursive, you can save some time and space by using the iterative version of the search.
The binary search is fast, so using recursion will not require much additional space for the recursive
calls. Also, coding the binary search recursively is somewhat easier than coding it iteratively. To con-
vince yourself of this, try to code an iterative version of the binary search. (See Exercise 6 at the end
of this chapter.)
C
HAPTER
S
UMMARY
A sequential search of either a list, an array, or a chain looks at the first item, the second item, and so on until
it either finds a particular item or discovers that the item does not occur in the group.
●
The average-case performance of a sequential search is O(
n
).
●
Typically, you perform a sequential search iteratively, although a simple recursive approach is also possible.
●
A binary search of an array requires that the array be sorted. It looks first to see whether the desired item is at
the middle of the array. If it is not, the search decides in which half of the array the item can occur and
repeats this strategy on only this half.
●
A binary search is O(log
n
) in the worst case.
●
Typically, you perform a binary search recursively, although an iterative approach is also possible.
●
A binary search of a linked chain of nodes is impractical.
●
P
ROGRAMMING
T
IP
Classes that implement the
Comparable
interface must define a
compareTo
method. Such classes should also
define an
equals
method that overrides the
equals
method inherited from
Object
. Both
compareTo
and
equals
should use the same test for equality. The method
binarySearch
in Segment 18.13 calls both the
method
equals
and the method
compareTo
. If the objects in the array did not have an appropriate
equals
method,
binarySearch
would not execute correctly. Note, however, that you could use
compareTo
instead of
equals
to test for equality.
●
E
XERCISES
1.
Revise the recursive method
search
, as given in Segment 18.6, so that it looks at the last entry in the array instead
of the first one.
2.
When searching a sorted array sequentially, you can ascertain that a given item does not appear in the array
without searching the entire array. For example, if you search the array
2 5 7 9
for 6, you can use the approach described in Segment 18.8. That is, you compare 6 to 2, then to 5, and finally to 7.
Since you did not find 6 after comparing it to 7, you do not have to look further, because the other entries in the array
are greater than 7 and therefore cannot equal 6. Thus, you do not simply ask whether 6 equals an array entry, you
also ask whether it is greater than the entry. Since 6 is greater than 2, you continue the search. Likewise for 5. Since
6 is less than 7, you have passed the point in the array where 6 would have had to occur, so 6 is not in the array.
a.
Write an iterative method
contains
to take advantage of these observations when searching a sorted array
sequentially.
b.
Write a recursive method
search
that a method
contains
can call to take advantage of these observations
when searching a sorted array sequentially.
