Search algorithm: Difference between revisions

Revision as of 01:36, 10 December 2001

Revision as of 15:51, 25 February 2002

Line 1:

'''Search algorithm'''s are [[algorithm|algorithms]] that find one element of a set by some key (perhaps containing other information related to the key). As this is a common problem in [[computer science]], the [[computational complexity]] of searching algorithms has been well studied.

The simplest search algorithm is [[linear search]]. It has [[big O|O]](n) running time, but can operate on a list containing the elements of the set.

A more sophisticated search algorithm is [[binary search]]. It runs in [[big O|O]](log(n)). This is significantly better than [[linear search]] for large lists of data, but it requires that the list be sorted before searching (see [[sort algorithm]]) and also be [[random access]].

[[Interpolation search]] is better than binary search for large sorted lists.

There is a family of [[tree]] search algorithms that compare ordered keys with one another to see if they are greater or less; the simplest one uses a [[binary search tree]]; and there is a family of tree [[data structure|data structures]] known as [[trie|tries]] that don't require a key compare until the end of the search.

[[Hash table|Hash tables]] are also used for search; they are the method of choice in most circumstances today.

There are also [[string search algorithms]], which are related but different.

[[Grovers algorithm|Grover's algorithm]] is a [[quantum computer|quantum algorithm]] that offers quadratic speedup over the classical linear search for unsorted lists.