O'Reilly logo

Algorithms in a Nutshell by Gary Pollice, Stanley Selkow, George T. Heineman

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 eU 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, kU, and the ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required