Jump to content

Talk:Search algorithm

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by 134.71.47.130 (talk) at 22:07, 9 February 2011 (→‎Missing section(s): new section). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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


(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)[reply]


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)[reply]

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)[reply]


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

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)[reply]

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

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

Missing section(s)

adversarial search redirects here, but there is nothing in the article about it.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Talk:Search_algorithm&oldid=412989691"