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;
    end
    return false
end

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
Quackery

... are herbal medicines. These are usually harmless, and do not claim to treat anything important. In most countries there is no regulation of herbal medicines. Some herbal ...

 
 
 
This page was created in 57.9 ms