Algorithms in a Nutshell

105

Chapter 5. Searching....................................................................................................................................................................

5

Searching

Overview

Given a collectionCof elements, there are three fundamental queries one might

ask:

Existence: Does C contain a target element t?

Given a collectionC, one often simply wants to know whether the collection

already contains a given value,t. The response to such a query istrueif an

element exists in the collection that matches the desired targett,orfalseif

this is not the case.

Retrieval: Return the element in C that matches the target element t

When complex elements are stored in a collection, the definition of a

“matching” element can be based on a key value for the element or a subset

of that element’s attributes. For example, when searching a collection of

information for the department of motor vehicles, one might only need to

provide the driver’s license number to retrieve the full information for that

licensed driver.

Associative lookup: Return information associated in collection C with the target key

element k

It is common to store additional pieces of information for complex struc-

tures. One can associate additional information with each key elementkin

the collection, which can be retrieved (or manipulated) as needed.

For the algorithms discussed in this chapter we assume the existence of a setU

that contains valuese∈Ubeing sought. The collectionCcontains elements drawn

fromU, and the target element being sought,t, is a member ofU.Iftis instead a

key value, then we considerUto be the set of potential key values,k∈U, and the

collectionCmay contain more complex elements. Note that duplicate values may

exist withinC, so it cannot be treated as a set (which only supports unique

membership).

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