Algorithms: Linear Search
Posted on: July 26, 2006 at 12:00 AM
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
}
|