- Search algorithm
In

computer science , a**search algorithm**, broadly speaking, is analgorithm that takes a problem asinput and returns a solution to the problem, usually after evaluating a number of possible solutions. Most of the algorithms studied by computer scientists that solve problems are kinds of search algorithms. The set of all possible solutions to a problem is called thesearch space .Brute-force search or "naïve"/uninformed search algorithms use the simplest method of searching through the search space, whereas informed search algorithms useheuristic function s to apply knowledge about the structure of thesearch space to try to reduce the amount of time spent searching.**Uninformed search**An uninformed search algorithm is one that does not take into account the specific nature of the problem. As such, they can be implemented in general, and then the same

implementation can be used in a wide range of problems thanks to abstraction. The drawback is that mostsearch space s are extremely large, and an uninformed search (especially of a tree) will take a reasonable amount of time only for small examples. As such, to speed up the process, sometimes only an informed search will do.**List search**List search algorithms are perhaps the most basic kind of search algorithm. The goal is to find one element of a set by some key (perhaps containing other information related to the key). As this is a common problem in

computer science , thecomputational complexity of these algorithms has been well studied. The simplest such algorithm islinear search , which simply examines each element of the list in order. It has expensive O(n) running time, where "n" is the number of items in the list, but can be used directly on any unprocessed list. A more sophisticated list search algorithm isbinary search ; it runs in O(log "n") time. This is significantly better thanlinear search for large lists of data, but it requires that the list be sorted before searching (seesorting algorithm ) and also berandom access .Interpolation search is better than binary search for large sorted lists with fairly even distributions, but has a worst-case running time of O("n").Grover's algorithm is a quantum algorithm that offers quadratic speedup over the classical linear search for unsorted lists. However, it requires a currently non-existent quantum computer on which to run.Hash table s are also used for list search, requiring onlyconstant time for search in the average case, but more space overhead and terrible O("n") worst-case search time. Another search based on specialized data structures usesself-balancing binary search tree s and requires O(log "n") time to search; these can be seen as extending the main ideas of binary search to allow fast insertion and removal. Seeassociative array for more discussion of list search data structures.Most list search algorithms, such as linear search, binary search, and self-balancing binary search trees, can be extended with little additional cost to find all values less than or greater than a given key, an operation called "range search". The glaring exception is hash tables, which cannot perform such a search efficiently.

**Tree search**Tree search algorithm s are the heart of searching techniques for structured data. These search trees of nodes, whether that tree is explicit or implicit (generated on the go). The basic principle is that a node is taken from adata structure , its successors examined and added to the data structure. By manipulating the data structure, the tree is explored in different orders - for instance, level by level (breadth-first search ) or reaching aleaf node first and backtracking (depth-first search ). Other examples of tree-searches include iterative-deepening search,depth-limited search ,bidirectional search , anduniform-cost search .It should be realized that the efficiency of a tree search (compared to other search methods) is highly dependent upon the number and structure of nodes in relation to the number of items on that node. If there are a large number of items on one or more nodes, there may well be a requirement to utilize a specific different search technique for locating items within that particular set. In other words, a tree search is not mutually exclusive with any other search technique that may be used for specific sets. It is simply a method of reducing the number of relevant items to be searched (by whatever method) to those within certain branches of the tree. For example, the

Greater London telephone directory may still contain entries for 20,000+ people whose surname is 'SMITH' belonging on a tree branch 'surnames beginning S'. The list of names may, or may not be, further subdivided by subscribers initials. Abinary search may be appropriate to locate a particular person with forename 'Alias' and perhaps thereafter alinear search to locate a particular address.**Graph search**Many of the problems in

graph theory can be solved usinggraph traversal algorithms, such asDijkstra's algorithm ,Kruskal's algorithm , thenearest neighbour algorithm , andPrim's algorithm . These can be seen as extensions of the tree-search algorithms.**Informed search**In an informed search, a heuristic that is specific to the problem is used as a guide. A good heuristic will make an informed search dramatically out-perform any uninformed search.

There are few prominent informed list-search algorithms. A possible member of that category is a hash table with a hashing function that is a heuristic based on the problem at hand. Most informed search algorithms explore trees Fact|date=August 2008. These include

best-first search , and A*. Like the uninformed algorithms, they can be extended to work for graphs as well.**Adversarial search**In games such as

chess , there is agame tree of all possible moves by both players and the resulting board configurations, and we can search this tree to find an effective playing strategy. This type of problem has the unique characteristic that we must account for any possible move our opponent might make. To account for this, game-playing computer programs, as well as other forms ofartificial intelligence likemachine planning , often use search algorithms like theminimax algorithm ,search tree pruning , andalpha-beta pruning .**Constraint satisfaction**This is a type of search which solves

constraint satisfaction problem s where, rather than looking for a path, the solution is simply a set of values assigned to a set of variables. Because the variables can be processed in any order, the usual tree search algorithms are too inefficient. Methods of solving constraint problems includecombinatorial search andbacktracking , both of which take advantage of the freedom associated with constraint problems. Common tricks or techniques involved inbacktracking is Constraint propagation, which is a general form of Forward checking. Other local search algorithms, such as generic algorithm, which minimize the conflicts, also do a good job.**Other types***

String searching algorithm s search for patterns within strings; one popular data structure that makes this more efficient is thesuffix tree

*Genetic algorithms andGenetic programming use ideas fromevolution as heuristics for reducing the search space

*Sorting algorithm s necessary for executing certain search algorithms

*Simulated annealing is aprobabilistic search algorithm

*Recommender system s also use statistical methods to rank results in very large data sets

*Tabu search is a technique to avoid discrete searches getting stuck in local minima

*Federated search

*Minimax which can be highly optimized usingalpha-beta pruning is an algorithm to search for good moves inzero-sum games

*Ternary search **ee also***

Selection algorithm

*No free lunch in search and optimization

*Secretary problem is an online (ie sequentially presented) search problem with imperfect information, and a statistically optimal strategy.**External links*** [

*http://www.gp-field-guide.org.uk/ A Field Guide to Genetic Programming*] by Poli, Langdon, and McPhee. Available as a free PDF, or in printed form from Lulu.com.

* [*http://en.wikiversity.org/wiki/Uninformed_Search_Project Self-Guided Lesson on Uninformed Search*] Go to the Wikiversity and teach yourself to program an uninformed search solution.

*Wikimedia Foundation.
2010.*