Content deleted Content added
m Fixed the link to 'String search algorithms' |
m links |
||
Line 2:
'''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 notation|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 notation|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. However, the underlying data structure must allow such kind of searching.
| |||