Essential Algorithms, 2nd Edition

CHAPTER 7Searching

The preceding chapter explained how you can sort data. Algorithms such as quicksort and heapsort let you sort 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 word in a dictionary containing tens of thousands of words in just a minute or two because all the words are arranged in sorted order. (Imagine trying to find a word if the dictionary 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. Chapter 10, “Trees,” discusses algorithms for working with trees.

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 searching 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 search ...