Talk:Search algorithm

Wiki Education Foundation-supported course assignment

This article was the subject of a Wiki Education Foundation-supported course assignment, between 20 January 2021 and 2 May 2021. Further details are available on the course page. Student editor(s): Rjrno3300.

Above undated message substituted from Template:Dashboard.wikiedu.org assignment by PrimeBOT (talk) 08:50, 17 January 2022 (UTC)

Search broken

Can anyone help? For some reason our wiki search does not return any results.

Even if I search for the exact wiki page - no results are displayed.

Last week it was working fine and produced the correct results. I have checked with our

Systems Administrator and had confirmation that nothing was changed over the weekend.

Thanks in advance for your help lenaquin@orbisuk.com — Preceding unsigned comment added by Lenaquin (talk • contribs) 10:25, 25 July 2005 (UTC)

@Lenaquin: This is the wrong page to ask about Wikipedia's search engine; this talk page is for discussing improvements to the Wikipedia article Search algorithm. If the question is about a local copy of Mediawiki, the place to go is probably the mediawiki.org web site. -- Beland (talk) 05:25, 8 August 2016 (UTC)

Combinatorial Search

(This notice also posted to Talk: Combinatorial search) How much overlap does this page have with combinatorial search? Do they deserve a merging? Is one of these article titles inappropriate? Should one link to the other?

Derrick Coetzee 21:31, 4 May 2004 (UTC)

Combinatorial Search Algorithms are a subset of Search Algorithms; Combinatorial Search could refer to the search problem rather than the algorithm used to solve it. The two articles should not be merged or directly linked. Headstogether 13:47, 8 November 2005 (UTC)

Grover's Algorithm

The mention of Grover's Algorithm, and quantum computing is somewhat misleading. It states that Grover's algorithm 'provides a solution' in polynomial time. It does no such thing: It is a theoretical model of a non-existant computing system. Maybe some day there will be quantum computers, but until then, an algorithm that runs only on a non-existant quantum computer exists only in the realm of theory.AngleWyrm 05:20, 10 August 2007 (UTC)

Quantum

Quantum computers exist now, and one has been sold commercially. 19:56, 10 September 2011 (UTC) — Preceding unsigned comment added by 108.194.44.134 (talk)

Removed

Removed the questionable sections on "SQL search" and "tradeoff search", which are subtopics at best. Bryan Silverthorn (talk) 20:56, 10 December 2007 (UTC)

Some missing points

• relationship between search and optimisation
• local vs global search, local optima
• soundness and completeness of search

Pgr94 (talk) 10:42, 15 April 2008 (UTC)

General reorganization

The topic "search algorithm" is too vast to discuss in detail in a single article, so I have reorganized it into an overview of the major classes of search problems and algorithms, with only a few *examples* of each class. Detailed discussions, such as complexity or applications, are best left to the articles on individual caetgories or individual methods.
The material that could not be used is temproarily copied below. It should be merged eventually into the relevant articles, such as linear search and tree search algorithm.

---

List search

Lists, and sequences generally, are perhaps the most commonly encountered data structures; search algorithms adapted for them are common as well. The goal is to find one element of a set (i.e., from the list) by some criterion (typically called a key and perhaps containing other information related to it). As this is a common problem in computer science, the computational complexity of these algorithms has been intensively studied.

The simplest such algorithm is linear search, which examines each element of the list as they are encountered. It is expensive in running time compared to many other algorithms: in O(n), where n is the number of items in the list. It can be used directly on any unprocessed list, regardless of history, which is sometimes useful. A more sophisticated list search algorithm is binary search; it runs in O(log n) time. This is significantly better than linear search for large lists, but is sometimes useful for surprisingly small ones given its increase in speed. But it requires the list be sorted before searching (see sorting algorithm) and generally, that the list be randomly accessible. This last may force lengthy (ie, time expensive) reads of mass storage before a binary search can be started. Interpolation search is better than binary search for large sorted lists with 'fairly even' key distributions (O(log (log n)) complexity), but has a worst-case running time of O(n).

Hash tables can also be used for list searches. They run in constant time in the average case, but have terrible worst-case time (O(n)) In addition, more space and time is required to set up such tables. Another search based on specialized data structures uses self-balancing binary search trees and needs only O(log n) time. Such tree searches can be seen as extending the ideas of binary search to allow fast insertion and removal in the data structures. See associative array for more discussion of list search data structures.

Most list search algorithms, such as linear search, binary search, and self-balancing binary search trees, can be extended with little additional cost to find all values less than or greater than a given key, an operation called range search. One such exception is hash tables, which cannot perform such searches efficiently.

Tree search

Tree search algorithms are likely the most used searching techniques for structured data. They examine trees of nodes, whether the tree is explicit or implicit (ie, generated by the search algorithm's execution). The basic principle is that a node is taken from a data structure, its successors examined and added to the data structure. By manipulating the data structure, the tree can be explored in different orders. For instance, level by level (ie, breadth-first search) or reaching a leaf node first and backtracking (ie, depth-first search), etc. Other examples of tree-searches include iterative-deepening search, depth-limited search, bidirectional search, and uniform-cost search.

The efficiency of a tree search is highly dependent upon the number and structure of nodes in relation to the number of items on that node. If there are a large number of items on one or more nodes, there may well be a requirement to use a specific different search technique for locating items within that particular set to attain adequate performance. In other words, a tree search is not mutually exclusive with any other search technique that may be used for specific sets. It is a method of reducing the number of relevant items to be searched to those within certain branches of the tree, thus reducing running time. For example, the Greater London telephone directory may contain entries for 20,000+ people whose surname is 'Smith' belonging on a tree branch on which are found 'surnames beginning S'. The list of names may, or may not be, further ordered (ie, structured) by subscribers first names or initials. A binary search may be appropriate to locate a particular person with given name 'Alice' and perhaps thereafter a linear search to locate a particular address for a specific Alice Smith.

See also

• Ternary search
• Search suggest drop-down list
• Secretary problem is an online (i.e. sequentially presented) search problem with imperfect information, and a statistically optimal strategy
• Odds algorithm is a general online search–selection algorithm for random input.
• Princess and monster game

---

All the best, --Jorge Stolfi (talk) 17:58, 4 January 2010 (UTC)

Missing section(s)

adversarial search redirects here, but there is nothing in the article about it. —Preceding unsigned comment added by 134.71.47.130 (talk) 22:07, 9 February 2011 (UTC)

Algorithms discussion - can we make this more exhaustive and hierarchical?

There exists a wide expanse of algorithm and discussion on wikipedia. But it's difficult to find a lot of them without finding them first on some other discussion site. Therefore, I suggest (and I'm doing it here since I could not get to the 'talk' section of 'algorithm' page on wikipedia) that we collect all the algorithms we have on here, and make them hierarchical by category. What I mean is, Algorithm page -> sub-topics: search algorithms, sorting algorithms, graph algorithms, generic algorithms, etc. Generic Algorithms -> sub-topics-generic programming algorithms: arrays, lists, linked lists, etc. Search algorithms -> sub-topics: disk-based searching, in-memory searching Graph algorithms -> sub-topics: Sorting algorithms -> sub-topics:

You get the idea. This way, if people are wanting to discover what's new or what's old, where we've been and where things are going, or just want to endulge themselves in algorithms and computer techniques, they can just start at one of these pages and work their way down to more detailed discussions from there. These should all go back to the 'algorithm' page on wikipedia, as a starting point. 'See also' at the bottom of course can still link to related topics....

Just a suggestion that would make wikipedia's algorithms arsenal more efficient to find and search/browse through... 75.133.175.2 (talk) 06:29, 30 October 2013 (UTC)

Calling for expert attention

This article is stalled at a level of expertise and degree of quality of organization and sourcing that is markedly subpar, and so I have called for expert attention. The article has for some time been essentially a hodgepodge listing of various ideas and approaches in the subject area, strung together as Wikilinks, rather than a well-structured, externally sourced encyclopedic article.

As well, the only source currently listed, Knuth (at Stanford, reference to which I completed today, to make fully accessible)--while a fine starting point--does not appear anywhere as an inline citation, and is, at this point in time, over 15 years old. This, I would note, is a significant percentage of the overall lifetime of the subject matter's history itself.

Bottom line, the article needs to be re-structured by an expert, with standard contemporary academic sources added, with much of the extraneous linked material removed, so that it is a stand-alone, substantive encyclopedia article useful to a lay-reader. Leprof 7272 (talk) 16:48, 13 December 2014 (UTC)