In computer science, a search algorithm, broadly speaking, is an algorithm that takes a problem as input and returns a solution to the problem. 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 the search space. Brute-force search or "naive" search algorithms use the simplest, most intuitive method of searching through the search space, whereas search algorithms that use heuristics apply knowledge about the structure of the search space to try to reduce the amount of time spent searching.
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, the computational complexity of these algorithms has been well studied. The simplest such algorithm is linear 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 is binary search; it runs in O(log n) time. This is significantly better than linear search for large lists of data, but it requires that the list be sorted before searching (see sort algorithm) and also be random access. Interpolation search is better than binary search for very large sorted lists with fairly even distributions. Grover's algorithm is a quantum algorithm that offers quadratic speedup over the classical linear search for unsorted lists.
Hash tables are also used for list search, requiring only constant 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 uses self-balancing binary search trees 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. See associative 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 algorithms search nodes of trees. Examples include Depth-first search, Breadth-first search, Best-first search, and A*.
Many of the problems in graph theory can be solved using search algorithms, such as Dijkstra's algorithm, Kruskal's algorithm, the nearest neighbour algorithm, and Prim's algorithm.
Game-playing computer programs and other forms of artificial intelligence like machine planning and often use search algorithms like the Minimax algorithm, search tree pruning, and alpha-beta pruning.
String searching algorithms search for patterns within strings; one popular data structure that makes this more efficient is the suffix tree.
Genetic algorithms use ideas from evolution as heuristics for reducing the search space.
Simulated annealing is a probabilistic search algorithm.