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:
def linear_search(array, value)
array.each { |element|
return true if element == value
}
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;
}
Here is another example in Java:
public static boolean linear_search(Comparable array, Comparable value) {
for(Comparable c : array) {
if(c.compareTo(value) == 0)
return true;
}
return false;
}
Here is another example in Python
def LinearSearch(array, value):
for i in array:
if i == value:
return True
else:
return False
And here is a sample implementation in C++ using templates and STL containers:
template <class C, typename T>
bool linear_search(const C& array, const T& value) {
C::const_iterator iter = array.begin();
C::const_iterator end = array.end();
while (iter != end) {
if (*iter == value)
return true;
++iter;
}
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.de:Lineare Suche it:Ricerca sequenziale ja:線型探索 fi:Lineaarihaku