Linear search

related topics
{math, number, function}
{rate, high, increase}

In computer science, linear search or sequential search is a method for finding a particular value in a list, that consists of checking every one of its elements, one at a time and in sequence, until the desired one is found.[1]

Linear search is the simplest search algorithm; it is a special case of brute-force search. Its worst case cost is proportional to the number of elements in the list; and so is its expected cost, if all list elements are equally likely to be searched for. Therefore, if the list has more than a few elements, other methods (such as binary search or hashing) may be much more efficient.

Contents

Analysis

For a list with n items, the best case is when the value is equal to the first element of the list, in which case only one comparison is needed. The worst case is when the value is not in the list (or occurs only once at the end of the list), in which case n comparisons are needed.

If the value being sought occurs k times in the list, and all orderings of the list are equally likely, the expected number of comparisons is

For example, if the value being sought occurs once in the list, and all orderings of the list are equally likely, the expected number of comparisons is \frac{n + 1}2. However, if it is known that it occurs once, than at most n - 1 comparisons are needed, and the expected number of comparisons is

(for example, for n = 2 this is 1, corresponding to a single if-then-else construct).

Either way, asymptotically the worst-case cost and the expected cost of linear search are both O(n).

Non-uniform probabilities

The performance of linear search improves if the desired value is more likely to be near the beginning of the list than to its end. Therefore, if some values are much more likely to be searched than others, it is desirable to place them at the beginning of the list.

In particular, when the list items are arranged in order of decreasing probability, and these probabilities are geometrically distributed, the cost of linear search is only O(1). If the table size n is large enough, linear search will be faster than binary search, whose cost is O(log n).[1]

Full article ▸

related documents
Closure (topology)
Procedural programming
Arity
Riesz representation theorem
Constructible number
Octal
Union (set theory)
Gram–Schmidt process
Compactness theorem
Depth-first search
Open set
Recursive descent parser
Hyperbolic function
Integral domain
Compactification (mathematics)
Bolzano–Weierstrass theorem
Augmented Backus–Naur Form
Decimal
Pauli matrices
Legendre polynomials
Compact space
Elliptic integral
Chain complex
Commutator subgroup
Perfect number
Fixed point combinator
Paracompact space
Rank (linear algebra)
Jules Richard
Existential quantification