Algorithms in a Nutshell

(^106) | Chapter 5: Searching
As we will see, it is important to know whether one can randomly access any indi-
vidual element inCor whether one can only iterate over the elements one by one.
When the collection allows for indexing of arbitrary elements, we use the nota-
tionAto represent the collection and the notationA[i] to represent theithelement
ofA. By convention, we use the valuenilto represent an element not inU; such a
value is useful when a search is asked to return a specific element in a collection
but that element is not present. In general, we assume it is impossible to search for
nil in a collection—that is,t≠nil.
The algorithms in this chapter describe specific ways to structure data to more
efficiently process these kinds of queries. One approach to consider is to order the
collectionCusing the sorting algorithms covered in Chapter 4. As we will see, the
efficiency of the queries does improve, but there are other costs involved in main-
taining a sorted collection, especially when there may be frequent insertions or
deletions of elements in the collection. You should choose an appropriate struc-
ture that not only speeds up the performance of individual queries but also
reduces the overall cost of maintaining the collection structure in the face of both
dynamic access and repeated queries.
Sequential Search
SEQUENTIALSEARCH, also calledlinear search, is the simplest of all searching
algorithms. It is a brute-force approach to locating a single target value,t, in some
collection,C. It findstby starting at the first element of the collection and exam-
ining each subsequent element until either the matching element is found or each
element of the collection has been examined.
Consider the case of a moderate-size restaurant with 10–20 tables that requires
reservations for all customers. The restaurant is close to a large medical center,
and many of its customers are medical staff of the center or family members of
patients at the center. The restaurant advertises that they will locate any patron in
case of emergency and deliver messages to that person promptly. When customers
are seated at a designated table, the hostess records the names of the customers
with that table and erases the names when the party leaves. To locate a patron in
the restaurant at any given moment, the hostess simply scans through the infor-
mation for the collection of tables.
Input/Output
There must be some way to obtain each element from the collection being
searched; the order is not important. If a collectionAsupports indexing, then an
index valueican be used to retrieve elementA[i]. Often a collectionCis acces-
sible by using a read-onlyiteratorthat retrieves each element fromC(as, for
example, a database cursor in response to an SQL query). Accessing the elements
by the iterator is described in the lower half of Figure 5-1.
Input
The input consists of a collection,C,ofn≥0 elements and a target item,t, that is
sought.
Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.
Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use