Linear search

In 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:

\ndef linear_search(array, value)\n    for element in array\n        return true if element == value\n    end\n    return false\nend\n

Here is a sample implementation in PHP:\n

\nfunction linear_search($array, $value)\n{\n    foreach ($array as $current) {\n        if ($current == $value) {\n            return TRUE;\n        }\n    }\n    return FALSE;\n}\n

And here is a sample implementation in C++ using templates and STL containers:\n

\ntemplate \nbool linear_search(const C& array, const T& value) {\n    C::const_iterator iter = array.begin();\n    C::const_iterator end = array.end();\n    while (iter != end) {\n        if (*iter == value)\n            return true;\n        ++iter;\n    }\n    return false;\n}\n

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. Category:Algorithms\n