Java Reference
In-Depth Information
P
eople are always looking for something, be it a date, a mate, or a lost sock. In fact, searching is one of
the most common tasks done for us by computers. Just think of how many times you search the Internet.
This chapter looks at two simple search strategies, the sequential search and the binary search. You can
use these strategies when implementing the method
contains
for either the ADT list or the ADT sorted
list. A binary search is usually much faster than a sequential search when the data is in an array rather
than a chain of linked nodes and when the data is sorted. Sorting data, however, usually takes much more
time than searching it. This fact should influence your choice of search method in a given situation.
18.1
Like the people in Figure 18-1, you can search your desk for a pen, your closet for your favorite
sweater, or a list of names to see whether you are on it. Searching for a particular item—called the
target
—among a collection of many items is a common task.
FIGURE 18-1
Searching is an everyday occurrence
Let's find your name on that list. If
nameList
is an instance of an ADT list whose entries are
names, we can search it by using the list operation
contains
. Recall that this method is boolean-
valued and returns true if a given item is in the list.
The implementation of
contains
depends upon how we store the list entries. Among the
implementations of the ADT list given in Chapters 13 and 14 is one that stores the list's entries in
an array and another that uses a chain of linked nodes. Let's look at the array first.
18.2
As Segment 13.13 of Chapter 13 mentioned, a sequential search of a list compares the desired item—
the target—with the first entry in the list, the second entry in the list, and so on until it either locates the
desired entry or looks at all the entries without success. In an array-based implementation of the list, we
search the array that contains the list's entries. We can implement this search either iteratively or recur-
sively. This section looks at both approaches and examines their efficiencies.
