# 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