Home Java Java-tips Algorithms Searching Algorithms: Linear Search

Ask Questions?

View Latest Questions

Advertisement


 
 

Algorithms: Linear Search
Posted on: July 26, 2006 at 12:00 AM
Linear search is a good solution because it's so straightforward.

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
Copyleft 2006 Fred Swartz MIT License
Advertisement


DMCA.com