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. Computer science is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... In computer science, a search algorithm, broadly speaking, is an algorithm that takes a problem as input and returns a solution to the problem, usually after evaluating a number of possible solutions. ...

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. It has been suggested that Landau notation be merged into this article or section. ...

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: Objective Caml (OCaml) is a general-purpose programming language descended from the ML family, created by Xavier Leroy, Jérôme Vouillon, Damien Doligez, Didier Rémy and others in 1996. ...

 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: This article is about computer software. ...

 Mem[x_, {___, 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. In computer science, binary search or binary chop is a search algorithm for finding a particular value in a linear array, by ruling out half of the data at each step. ...

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. A binary tree, a simple type of branching linked data structure. ... In computer science, a hash table is a data structure that speeds up searching for information by a particular aspect of that information, called a key. ...

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.