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

## Related Pages

Binary Search