Mastering Algorithms with Perl

Chapter 5.  Searching

The right of the people to be secure against unreasonable searches and seizures, shall not be violated....

—Constitution of the United States, 1787

Computers—and people—are always trying to find things. Both of them often need to perform tasks like these:

• Select files on a disk

• Find memory locations

• Identify processes to be killed

• Choose the right item to work upon

• Decide upon the best algorithm

• Search for the right place to put a result

The efficiency of searching is invariably affected by the data structures storing the information. When speed is critical, you’ll want your data sorted beforehand. In this chapter, we’ll draw on what we’ve learned in the previous chapters to explore techniques for searching through large amounts of data, possibly sorted and possibly not. (Later, in Chapter 9, we’ll separately treat searching through text.)

As with any algorithm, the choice of search technique depends upon your criteria. Does it support all the operations you need to perform on your data? Does it run fast enough for frequently used operations? Is it the simplest adequate algorithm?

We present a large assortment of searching algorithms here. Each technique has its own advantages and disadvantages and particular data structures and sorting methods for which it works especially well. You have to know which operations your program performs frequently to choose the best algorithm; when in doubt, benchmark and profile your programs to find out.

There are two general ...