Algorithms: A Linear Search

Algorithms: A Linear Search

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 isreturned.

For small arrays, a linear search is a good solution because it’s so straightforward. In an array of a million elements, a linear search will take, on average, 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


Share the Post: