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.
Search Encyclopedia

Featured Article
