Search algorithm: Difference between revisions

Revision as of 09:02, 15 July 2022

Latest revision as of 04:10, 18 August 2025

(42 intermediate revisions by 33 users not shown)

Line 4:

{{More citations needed|date=April 2016}}

}}

[[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]] (if more than one, algorithms<ref>{{Cite web|last=Davies|first=Dave|date=May 25, 2020|title=How Search Engine Algorithms Work: Everything You Need to Know|url=https://www.searchenginejournal.com/search-engines/algorithms/#whysearc|url-status=live|access-date=27 March 2021|website=Search Engine Journal}}</ref>) designed to solve a [[search problem]]. Search algorithms work to retrieve information stored within particular [[data structure]], or calculated in the [[Feasible region|search space]] of a problem ___domain, with [[Continuous or discrete variable|either discrete or continuous values]].

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

While the search problems described above and [[web search]] are both problems in information retrieval, they are generally studied as separate subfields and are solved and evaluated differently. Web search problems are generally focused on filtering and finding documents highly relevant to human queries. Classic search algorithms are evaluated on how fast they can find a solution, and whether the solution found is optimal. Though information retrieval algorithms must be fast, the quality of [[Ranking (information retrieval)|ranking]], and whether good results have been left out and bad results included, is more important.

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 28:

* Finding a combination or password from the whole set of possibilities

* [[Factorization|Factoring]] an integer (an important problem in [[cryptography]])

* Search engine optimization (SEO) and content optimization for web crawlers

* Optimizing an industrial process, such as a [[chemical reaction]], by changing the parameters of the process (like temperature, pressure, and pH)

* Retrieving a record from a [[database]]

Line 40 ⟶ 41:

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]].

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]] <ref>{{Cite journal |last=Talukdar |first=Sarosh |last2=Baerentzen |first2=Lars |last3=Gove |first3=Andrew |last4=De Souza |first4=Pedro |date=1998-12-01 |title=Asynchronous Teams: Cooperation Schemes for Autonomous Agents |url=https://doi.org/10.1023/A:1009669824615 |journal=Journal of Heuristics |language=en |volume=4 |issue=4 |pages=295–321 |doi=10.1023/A:1009669824615 |issn=1572-9397|url-access=subscription }}</ref>, and [[genetic programming]], that combine arbitrary heuristics in specific ways. The opposite of local search would be global search methods. This method is applicable when the search space is not limited and all aspects of the given network are available to the entity running the search algorithm.<ref>{{Cite journal|last1=Hunter|first1=A.H.|last2=Pippenger|first2=Nicholas|date=4 July 2013|title=Local versus global search in channel graphs|journal=Networks: An International Journey|arxiv=1004.2526}}</ref>

This class also includes various [[Tree traversal|tree search algorithm]]s, that view the elements as vertices of a [[tree (graph theory)|tree]], and traverse that tree in some special order. Examples of the latter include the exhaustive methods such as [[depth-first search]] and [[breadth-first search]], as well as various heuristic-based [[Pruning (decision trees)|search tree pruning]] methods such as [[backtracking]] and [[branch and bound]]. Unlike general metaheuristics, which at best work only in a probabilistic sense, many of these tree-search methods are guaranteed to find the exact or optimal solution, if given enough time. This is called "[[Completeness (logic)|completeness]]".

Another important sub-class consists of algorithms for exploring the [[game tree]] of multiple-player games, such as [[chess]] or [[backgammon]], whose nodes consist of all possible game situations that could result from the current situation. The goal in these problems is to find the move that provides the best chance of a win, taking into account all possible moves of the opponent(s). Similar problems occur when humans or machines have to make successive decisions whose outcomes are not entirely under one's control, such as in [[robot]] guidance or in [[marketing]], [[finance|financial]], or [[military]] strategy planning. This kind of problem — [[combinatorial search]] — has been extensively studied in the context of [[artificial intelligence]]. Examples of algorithms for this class are the [[Minimax|minimax algorithm]], [[alpha–beta pruning]], and the [[A* search algorithm|A* algorithm]] and its variants.

===For sub-structures of a given structure===

The name "combinatorial search" is generally used for algorithms that look for a specific sub-structure of a given [[Discrete mathematics|discrete structure]], such as a graph, a [[string (computer science)|string]], a finite [[group (mathematics)|group]], and so on. The term [[combinatorial optimization]] is typically used when the goal is to find a sub-structure with a maximum (or minimum) value of some parameter. (Since the sub-structure is usually represented in the computer by a set of integer variables with constraints, these problems can be viewed as special cases of constraint satisfaction or discrete optimization; but they are usually formulated and solved in a more abstract setting where the internal representation is not explicitly mentioned.)

An important and extensively studied subclass are the [[List of algorithms#Graph algorithms|graph algorithm]]s, in particular [[graph traversal]] algorithms, for finding specific sub-structures in a given graph — such as [[Glossary of graph theory#Subgraphs|subgraphs]], [[path (graph theory)|paths]], circuits, and so on. Examples include [[Dijkstra's algorithm]], [[Kruskal's algorithm]], the [[nearest neighbour algorithm]], and [[Prim's algorithm]].

Another important subclass of this category are the [[string searching algorithm]]s, that search for patterns within strings. Two famous examples are the [[Boyer–Moore string -search algorithm|Boyer–Moore]] and [[Knuth–Morris–Pratt algorithm]]s, and several algorithms based on the [[suffix tree]] data structure.

===Search for the maximum of a function===

Line 58:

===For quantum computers===

There are also search methods designed for [[Quantum computing|quantum computer]]s, like [[Grover's algorithm]], that are theoretically faster than linear or brute-force search even without the help of data structures or heuristics. While the ideas and applications behind quantum computers are still entirely theoretical, studies have been conducted with algorithms like Grover's that accurately replicate the hypothetical physical versions of quantum computing systems.<ref>{{Cite journal|last1=López|first1=G V|last2=Gorin|first2=T|last3=Lara|first3=L|date=26 February 2008|title=Simulation of Grover's quantum search algorithm in an Ising-nuclear-spin-chain quantum computer with first- and second-nearest-neighbour couplings|journal=Journal of Physics B: Atomic, Molecular and Optical Physics|volume=41|issue=5|page=055504|doi=10.1088/0953-4075/41/5/055504|arxiv=0710.3196|bibcode=2008JPhB...41e5504L|s2cid=18796310}}</ref>

== Search engine optimization ==

{{Main|Search engine optimization}}

Search algorithms used in a search engine such as Google, order the relevant search results based on a myriad of important factors.<ref name=":0">{{Cite journal|last1=Baye|first1=Michael|last2=De los Santos|first2=Barbur|last3=Wildenbeest|first3=Matthijs|date=2016|title=Search Engine Optimization: What Drives Organic Traffic to Retail Sites?|journal=Journal of Economics & Management Strategy|volume=25|pages=6–31|doi=10.1111/jems.12141|s2cid=156960693}}</ref> [[Search engine optimization]] (SEO) is the process in which any given search result will work in conjunction with the search algorithm to organically gain more traction, attention, and clicks, to their site. This can go as far as attempting to adjust the search engines algorithm to favor a specific search result more heavily, but the strategy revolving around SEO has become incredibly important and relevant in the business world.<ref name=":0" />

==See also==

Line 86 ⟶ 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==

Line 95 ⟶ 93:

*[[Wikiversity:Uninformed Search Project|Uninformed Search Project]] at the [[Wikiversity]].

{{Refend}}

{{Algorithmic paradigms}}

[[Category:Internet search algorithms|Web search algorithms]]