Search algorithm: Difference between revisions

Revision as of 04:10, 10 October 2021

Revision as of 09:13, 28 November 2021

Line 5:

}}

[[File:Hash table 3 1 1 0 1 0 0 SP.svg|thumb|upright=1.2|Visual representation of a [[hash table]], a [[data structure]] that allows for fast retrieval of information.]]

In [[computer science]], a '''search algorithm''' is an [[algorithm]] (typically involving a multitude of other, more specific algorithms <ref>{{Cite web|last=Davies|first=Dave|date=May 25, 2020|title=How Search Engine Algorithms Work: Everything You Need to Know|url=https://www.searchenginejournal.com/search-engines/algorithms/#whysearc|url-status=live|access-date=27 March 2021|website=Search Engine Journal}}</ref>) which solves a [[search problem]]. Search algorithms work to retrieve information stored within some [[data structure]], or calculated in the [[Feasible region|search space]] of a problem ___domain, either with [[Continuous or discrete variable|either discrete or continuous values]].

While the search problems described above and [[web search]] are both problems in information retrieval, they are generally studied as separate subfields and are solved and evaluated differently. Web search problems are generally focused on filtering and finding documents that are most relevant to human queries. Classic search algorithms are typically evaluated on how fast they can find a solution, and whether that solution is guaranteed to be optimal. Though information retrieval algorithms must be fast, the quality of [[Ranking (information retrieval)|ranking]], and whether good results have been left out and bad results included, is more important.

The appropriate search algorithm often depends on the data structure being searched, and may also include prior knowledge about the data. SomeSearch databasealgorithms structurescan arebe speciallymade constructedfaster toor makemore searchefficient algorithmsby fasterspecially orconstructed moredatabase efficientstructures, such as a [[search tree]]s, [[hash map]]s, or aand [[database index]]es. {{Sfn|Beame|Fich|2002|p=39}}{{full citation needed|date=April 2021}}{{Sfn|Knuth|1998|loc=§6.5 ("Retrieval on Secondary Keys")}}

Search algorithms can be classified based on their mechanism of searching into 3three 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.{{Sfn|Knuth|1998|loc=§6.1 ("Sequential Searching")}} [[Binary search algorithm|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.{{Sfn|Knuth|1998|loc=§6.2 ("Searching by Comparison of Keys")}} Digital search algorithms work based on the properties of digits in data structures that use numerical keys.{{Sfn|Knuth|1998|loc=§6.3 (Digital Searching)}} Finally, [[Hash table|hashing]] directly maps keys to records based on a [[hash function]].{{Sfn|Knuth|1998|loc=§6.4, (Hashing)}}

Algorithms are often evaluated by their [[computational complexity]], or maximum theoretical run time. Binary search functions, for example, have a maximum complexity of {{math|''O''(log ''n'')}}, or logarithmic time. This means that the maximum number of operations needed to find the search target is a logarithmic function of the size of the search space.