Linear search

From Free net encyclopedia

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_, {___, x_, ___}] := True
Mem[_, _] := False

For implementations in real programming languages, see Linear search at Wikisource.

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.

[edit]

References

it:Ricerca sequenziale ja:線型探索 nl:Lineair zoeken pt:Busca linear sk:Lineárne vyhľadávanie fi:Lineaarihaku

Retrieved from "http://www.netipedia.com/index.php/Linear_search"