Search algorithm: Difference between revisions

Revision as of 00:05, 31 July 2017

Revision as of 11:45, 21 October 2017

Line 1:

{{Multiple issues|

{{Expert-subject needed|computer science|talk=Calling for expert attention|reason=longstanding subpar state of article structure and content, which is currently list based, dated, and non-encyclopedic, and without external sourcing |date=December 2014}}

{{specific|date=December 2014}}

{{Refimprove|date=April 2016}}

Line 7:

In [[computer science]], a '''search algorithm''' is any [[algorithm]] which solves the [[Search problem]], namely, to retrieve information stored within some data structure, or calculated in the [[Feasible region|search space]] of a [[problem ___domain]]. Examples of such structures include but are not limited to a [[Linked List]], an [[Array data structure]], or a [[Search tree]]. The appropriate search algorithm often depends on the data structure being searched, but also on any a priori knowledge about the data. Searching also encompasses algorithms that query the data structure, such as the SQL SELECT command.{{Sfn|Beame|Fich|2002|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.{{Sfn|Knuth|1998|loc=§6.1 ("Sequential Searching")}}[[#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 {{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.

Line 14:

===For virtual search spaces===

{{see also|Solver}}

Algorithms for searching virtual spaces are used in the 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 / equalities. 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 the structure of this space, such as linear relaxation, constraint generation, and [[Local consistency|constraint propagation]].

Line 76:

{{Computer shortcuts}}

[[Category:Search algorithms| ]]