C++ Notes: Algorithms: Linear Search
Look at every element
This is a very straightforward loop comparing every element in the
array with the key. As soon as an equal value is found, it returns.
If the loop finishes without finding a match, the search failed and
-1 is returned.
Performance
For small arrays, linear search is a good solution because it's
so straightforward.
In an array of a million elements linear search
on average will take 500,000 comparisons to find the key.
For a much faster search, take a look at
binary search.
Example
int linearSearch(int a[], int first, int last, int key) {
// function:
// Searches a[first]..a[last] for key.
// returns: index of the matching element if it finds key,
// otherwise -1.
// parameters:
// a in array of (possibly unsorted) values.
// first, last in lower and upper subscript bounds
// key in value to search for.
// returns:
// index of key, or -1 if key is not in the array.
for (int i=first; i<=last; i++) {
if (key == a[i]) {
return i;
}
}
return -1; // failed to find key
}
Related Pages
Binary Search