# Java 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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
/** Linear search of array for key. Returns index or -1 if not found. * The upperbound index is not included in the search. * This is to be consistent with the way Java in general expresses ranges. * This searches from low to high index values. * The performance is O(N). * @param a Array of values to be searched. * @param first Index of beginning of range. First element is a[first]. * @param upto Last element that is searched is a[upto-1]. * @param key Value that is being looked for. * @return Returns index of the first match, or -1 if no match. */ public static int linearSearch(int[] a, int first, int upto, int key) { for (int i = first; i < upto; i++) { if (key == a[i]) { return i; // Found key, return index. } } return -1; // Failed to find key } |