Given a collection C of elements, there are two fundamental queries:
Does C contain a target element? Given a collection C, we often simply want
to know whether the collection already contains a given element 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
Return information associated in collection C with a target key value k. A key is usually associated with a complex structure called a value. The lookup retrieves or replaces this value.
The algorithms in this chapter describe specific ways to structure data to more efficiently process search queries. For example, you might order the collection C using the sorting algorithms previously covered in Chapter 4. As we will see, sorting improves the performance of queries, but there are other costs involved in maintaining a sorted collection, especially when elements are frequently inserted or deleted.
Ultimately the performance is based on how many elements an algorithm inspects as it processes a query. Use the following guide to select the best algorithm for you:
Sequential Search offers the simplest implementation and is implemented as a basic construct in many programming languages. Use this algorithm when the collection is available only sequentially, as with an iterator.
When the collection is an array that doesn’t change and you want ...