Searching - Brief Idea

Searching algorithms have been studied nearly as much as sorting algorithms. The two are related in that many searching algorithms rely on the ordering of the data being searched. There are four basic kinds of searching algorithms:

• Sequential searching


• Comparison searching


• Radix searching


• Hashing

Each of these methods can be described using the same deck of cards example that was used for sorting.

In sequential searching, you go through the deck from top to bottom, looking at each card until you find the card you are looking for.

In comparison searching (also called binary searching), you start with an already sorted deck. You pick a card from the exact middle of the deck and compare it to the card you want. If it matches, you’re done. Otherwise, if it’s lower, you try the same search again in the first half of the deck. If it’s higher, you try again in the second half of the deck.

In radix searching, you deal the deck into the 13 piles as described in radix sorting. To find a desired card, you choose the pile corresponding to the desired rank and search for the card you want in that pile using any search method. Or you could deal the deck into 4 piles based on suit as described in radix sorting. You could then pick the pile according to the desired suit and search there for the card you want.

In hashing, you make space for some number of piles on the table, and you choose a function that maps cards into a particular pile based on rank and suit (called a hash function). You then deal all the cards into the piles, using the hash function to decide where to put each card. To find a desired card, you use the hash function to find out which pile the desired card should be in. Then you search for the card in that pile.

For instance, you might make 16 piles and pick a hash function like pile = rank + suit. If rank is a card’s rank treated as a number (ace = 1, 2 = 2, all the way up to king = 13), and suit is a card’s suit treated as a number (clubs = 0, diamonds = 1, hearts = 2, spades = 3), then for each card you can compute a pile number that will be from 1 to 16, indicating which pile the card belongs in. This technique sounds crazy, but it’s a very powerful searching method. All sorts of programs, from compression programs (such as Stacker) to disk caching programs (such as SmartDrive) use hashing to speed up searches for data.