The right of the people to be secure against unreasonable searches and seizures, shall not be violated....
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 ...