Algorithms in a Nutshell

Chapter 5. Searching

Overview

Given a collection C of elements, there are three fundamental queries one might ask:

Existence: Does C contain a target element t?

Given a collection C, one often simply wants to know whether the collection already contains a given value, t. The response to such a query is true if an element exists in the collection that matches the desired target t, or false if 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 structures. One can associate additional information with each key element k in the collection, which can be retrieved (or manipulated) as needed.

For the algorithms discussed in this chapter we assume the existence of a set U that contains values e∈U being sought. The collection C contains elements drawn from U, and the target element being sought, t, is a member of U. If t is instead a key value, then we consider U to be the set of potential key values, k∈U, and the ...