Linear search

Linear search is a search algorithm 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 is 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 sample implementation in Ruby:

def linear_search(array,value)
    i = 0
    while (i < array.size-1)
        if (array[i] == value)
            return true
        end
        i += 1
    end
    return false
end

Linear search is used to search an unordered list. Binary search is used to search an ordered list. If many searches are needed on an unchanging list, it may be faster to sort the list first, and then use Binary Search, which runs in O(log N).

/Talk