Search algorithm: Difference between revisions

Revision as of 20:47, 21 May 2017

Revision as of 19:07, 23 May 2017

Line 6:

}}

[[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]] that retrieves information stored within some data structure. Data structures can include linked lists, arrays, search trees, 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.{{Sfn|Beame|Fich|2001|p=39}}''{{Sfn|Knuth|1998|loc=§6.5 ("Retrieval on Secondary Keys")}}''

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 search algorithm|{{Sfn|Knuth|1998|loc=§6.1 ("Sequential Searching")}}]][[Search algorithm#cite note-FOOTNOTEKnuth1998.C2.A76.1 .28.22Sequential Searching.22.29-3|<span class="mw-reflink-text">[3]</span>]][[Search algorithm#cite note-FOOTNOTEKnuth1998.C2.A76.1 .28.22Sequential Searching.22.29-3|<span class="mw-reflink-text">[3]</span>]][[#cite_note-FOOTNOTEKnuth1998.C2.A76.1_(.22Sequential_Searching.22)-4|<span class="mw-reflink-text"><nowiki>[4]</nowiki></span>]] [[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)}} 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.

Line 15:

===For virtual search spaces===

Algorithms for searching virtual spaces are used in [[constraint satisfaction problem]], where the goal is to find a set of value assignments to certain variables that will satisfy specific mathematical [[equation]]s and [[inequation]]s / inequalities. They are also used when the goal is to find a variable assignment that will [[discrete optimization|maximize or minimize]] a certain function of those variables. Algorithms for these problems include the basic [[brute-force search]] (also called "naïve" or "uninformed" search), and a variety of [[heuristic function|heuristic]]s that try to exploit partial knowledge about structure of the space, such as linear relaxation, constraint generation, and [[Local consistency|constraint propagation]].

An important subclass are the [[Local search (optimization)|local search]] methods, that view the elements of the search space as the [[vertex (graph theory)|vertices]] of a graph, with edges defined by a set of heuristics applicable to the case; and scan the space by moving from item to item along the edges, for example according to the [[gradient descent|steepest descent]] or [[best-first search|best-first]] criterion, or in a [[Stochastic optimization|stochastic search]]. This category includes a great variety of general [[metaheuristic]] methods, such as [[simulated annealing]], [[tabu search]], A-teams, and [[genetic programming]], that combine arbitrary heuristics in specific ways.