Essential Algorithms: A Practical Approach to Computer Algorithms

CHAPTER 7

Searching

The preceding chapter explained how you can sort data. Algorithms such as quicksort and heapsort let you sort fairly large amounts of data quickly. Algorithms such as countingsort and bucketsort let you sort data almost as quickly as a program can examine it but only under certain special circumstances.

One of the advantages of sorted data is that it lets you find specific items relatively quickly. For example, you can locate a particular person in a telephone directory containing tens of thousands of names in just a minute or two because all the names are arranged in sorted order. (Imagine trying to find a name if the directory wasn't sorted!)

This chapter explains algorithms that you can use to find a particular piece of data in a sorted array.

NOTE The algorithms described in this chapter work with simple arrays, not more specialized data structures. Specialized data structures such as trees also let you quickly find an item with a specific value. Algorithms for working with trees are discussed in Chapter 10.

NOTE Some programming libraries include searching tools that locate items in a sorted array. For example, the .NET Framework's Array class provides a BinarySearch method. These methods generally are fast, so in practice you may want to use those tools to save time writing and debugging the sorting code.

It's still important to understand how searching algorithms work, however, because sometimes you can do even better than the tools. For example, interpolation ...