Types of Search Algorithms

Search algorithms form an important part of many programs. Some searches involve looking for an entry in a database, such as looking up your record in the IRS database. Other search algorithms trawl through a virtual space, such as those hunting for the best chess moves. Although programmers can choose from numerous search types, they select the algorithm that best matches the size and structure of the database to provide a user-friendly experience.

The linear search is the algorithm of choice for short lists, because it's simple and requires minimal code to implement. The linear search algorithm looks at the first list item to see whether you are searching for it and, if so, you are finished. If not, it looks at the next item and on through each entry in the list.

Binary search is a popular algorithm for large databases with records ordered by numerical key. Example candidates include the IRS database keyed by social security number and the DMV records keyed by driver's license numbers. The algorithm starts at the middle of the database -- if your target number is greater than the middle number, the search will continue with the upper half of the database. If your target number is smaller than the middle number, the search will continue with the lower half of the database. It keeps repeating this process, cutting the database in half each time until it finds the record. This search is more complicated than the linear search but for large databases it's much faster than a linear search.

A tree search only works if the data fits into a tree structure. The database starts at a root that goes to a few items, each of which goes to a few more items and so on until you have a tree. One example is the game of chess. The current board position is the root. The legal moves from this position represent one step down the tree, and so on until the player finds the board position that leaves him in the best position.

A genetic algorithm search is one of the techniques behind artificial intelligence. It searches for an "optimum solution" expressed as a string of data — such as the list of internal dimensions of a jet engine that provides maximum thrust. The search starts with a random population of strings and tests each one, keeping the best ones and breeding them to get the next generation. The program keeps repeating this process until it arrives at an optimum solution string.