# 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