Search algorithm: Difference between revisions

Revision as of 19:44, 15 August 2023

Revision as of 15:30, 26 September 2023

Line 9:

Although [[Search engine (computing)|search engines]] use search algorithms, they belong to the study of [[information retrieval]], not algorithmics.

The appropriate search algorithm to use often depends on the data structure being searched, and may also include prior knowledge about the data. Search algorithms can be made faster or more efficient by specially constructed database structures, such as [[search tree]]s, [[hash map]]s, and [[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 three 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 by using 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)}}

Line 82:

===Bibliography===

====Books====

{{sfn whitelist|CITEREFKnuth1998}}

*{{TAOCP|volume=3|edition=2}}

====Articles====

*{{Citecite journal|last1=SchmittouBeame|first1=ThomasPaul|last2=SchmittouFich|first2=Faith E.|dateauthor2-link=2002-08-01Faith Ellen|title = Optimal Bounds for the Predecessor Problem and Related Problems|journal=[[Journal of Computer and System Sciences]]|volume=65|issue=1|date=August 2002|pages=38–72|doi=10.1006/jcss.2002.1822|s2cid=1991980 |doi-access=free}}

*{{Cite journal|last1=Schmittou|first1=Thomas|last2=Schmittou|first2=Faith E.|date=2002-08-01|title=Optimal Bounds for the Predecessor Problem and Related Problems|journal=Journal of Computer and System Sciences|volume=65|issue=1|pages=38–72|doi=10.1006/jcss.2002.1822|doi-access=free |ref=none}}

==External links==