View source for Search algorithm

In [[computer science]], a '''search algorithm''' is an [[algorithm]] that retrieves [[information]] stored within some [[data structure]].

== Description ==

Data structures can include [[Linked list|linked lists]], [[Array data structure|arrays]], [[Search tree|search trees]], [[Hash table|hash tables]], or various other storage methods.

The appropriate search algorithm often depends on the data structure being searched. Searching also encompasses algorithms that query the data structure, such as the SQL SELECT command.

Search algorithms can be classified based on their mechanism of searching. Linear search algorithms check every record for the one associated with a target key in a linear fashion.

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.

Digital search algorithms work based on the properties of digits in data structures that use numerical keys.

Finally, hashing directly maps keys to records based on a hash function.

Searches outside of a linear search require that the data be sorted in some way.

Search functions are also evaluated on the basis of their complexity, or maximum theoretical run time. Binary search functions, for example, have a maximum complexity of 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.

== See also ==

* [[Category:Search algorithms]]
* [[Backward induction]]
* [[Content-addressable memory hardware]]
* [[Dual-phase evolution]]
* [[Linear search problem]]
* [[No free lunch in search and optimization]]
* [[Recommender system]]s also use statistical methods to rank results in very large data sets
* [[Search engine (computing)]]
* [[Search game]]
* [[Selection algorithm]]
* [[Solver]]
* [[Sorting algorithms]] necessary for executing certain search algorithms
* Web Searching e.g., Google's [[PageRank]]

== External links ==

* [https://en.wikipedia.org/wiki/Search_algorithm Search algorithm] @ Wikipedia

[[Category:Computer science]]