Sorting and Searching - Java Concepts - page 887

A linear search examines all values in an array until it finds a match or reaches the
end.

How long does a linear search take? If we assume that the element v is present in the
array a , then the average search visits n/2 elements, where n is the length of the array.
If it is not present, then all n elements must be inspected to verify the absence. Either
way, a linear search is an O(n) algorithm.

A linear search locates a value in an array in O(n) steps.

649
650

Here is a class that performs linear searches through an array a of integers. When
searching for the value v , the search method returns the first index of the match, or
-1 if v does not occur in a .

ch14/linsearch/LinearSearcher.java

1 /**
2 A class for executing linear searches through an array.
3 */
4 public class LinearSearcher
5 {
6 /**
7 Constructs the LinearSearcher.
8 @param anArray an array of integers
9 */
10 public LinearSearcher( int [] anArray)
11 {
12 a = anArray;
13 }
14
15 /**
16 Finds a value in an array, using the linear search
17 algorithm.
18 @param v the value to search
19 @return the index at which the value occurs, or -1
20 if it does not occur in the array
21 */