Encyclopedia > Linear search

  Article Content

Linear search

In the field of 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.

Here is a sample implementation in Ruby:

def linear_search(array,value)
    for i in array
        return true if i == value;
    return false

Here is a sample implementation in PHP:

function linear_search($array, $value)
    foreach ($array as $current) {
        if ($current == $value) {
            return TRUE;
    return 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.

All Wikipedia text is available under the terms of the GNU Free Documentation License

  Search Encyclopedia

Search over one million articles, find something about almost anything!
  Featured Article
Digital Rights Management

... Architecture scheme proposed by Intel and others is an example. So are several laws proposed or already enacted in various jurisidictions (State, Federal, non-US). ...

This page was created in 40.5 ms