Global InformationSearch algorithm information
 | This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages)
|
In computer science, a search algorithm is an algorithm designed to solve a search problem. Search algorithms work to retrieve information stored within particular data structure, or calculated in the search space of a problem domain, with either discrete or continuous values.
Although search engines use search algorithms, they belong to the study of information retrieval, not algorithmics.
The appropriate search algorithm to use often depends on the data structure being searched, and may also include prior knowledge about the data. Search algorithms can be made faster or more efficient by specially constructed database structures, such as search trees, hash maps, and database indexes.[1][2]
Search algorithms can be classified based on their mechanism of searching into three types of algorithms: linear, binary, and hashing. Linear search algorithms check every record for the one associated with a target key in a linear fashion.[3] Binary, or half-interval, searches repeatedly target the center of the search structure and divide the search space in half. Comparison search algorithms improve on linear searching by successively eliminating records based on comparisons of the keys until the target record is found, and can be applied on data structures with a defined order.[4] Digital search algorithms work based on the properties of digits in data structures by using numerical keys.[5] Finally, hashing directly maps keys to records based on a hash function.[6]
Algorithms are often evaluated by their computational complexity, or maximum theoretical run time. Binary search functions, for example, have a maximum complexity of O(log n), or logarithmic time. In simple terms, the maximum number of operations needed to find the search target is a logarithmic function of the size of the search space.
- ^ Beame & Fich 2002, p. 39.
- ^ Knuth 1998, §6.5 ("Retrieval on Secondary Keys").
- ^ Knuth 1998, §6.1 ("Sequential Searching").
- ^ Knuth 1998, §6.2 ("Searching by Comparison of Keys").
- ^ Knuth 1998, §6.3 (Digital Searching).
- ^ Knuth 1998, §6.4, (Hashing).