In computer science, linear search is a search algorithm, also known as sequential search, that is suitable for searching a set of data for a particular value.

It operates by checking every element of a list until a match is found. Linear search runs in O(N). If the data are distributed randomly, on average N/2 comparisons will be needed. The best case is that the value is equal to the first element tested, in which case only 1 comparison is needed. The worst case is that the value is not in the list, in which case N comparisons are needed.

The List module in the OCaml standard library defines a function called "mem" that returns true if the given element is in the given list or false if not. This function could be defined as:

let rec mem x = function
    * -> false
  | h :: t -> h=x || mem x t

Mathematica's unusually powerful pattern matching allows linear search to be implemented by a pattern match:

Mem{___, x_, ___} := True
Mem_ := False

Linear search can be used to search an unordered list. The more efficient binary search can only be used to search an ordered list.

If more than a small number of searches are needed, it is advisable to use a more efficient data structure. One approach is to sort and then use binary searches. Another common one is to build up a hash table and then do hash lookups.

References

• Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Section 6.1: Sequential Searching, pp.396–408.

Algorithms | Search_algorithms

Lineare Suche | Ricerca sequenziale | 線型探索 | Lineair zoeken | Busca linear | Lineárne vyhľadávanie | Lineaarihaku