Content deleted Content added
m Citation maintenance. |
Diego Moya (talk | contribs) Expand lede with body, search may also explore a calculated (not stored) ___domain |
||
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, or calculated in the [[Feasible region|search space]] of a [[problem ___domain]]. 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.
| |||