Searching and Sorting - Building Java Programs: A Back to Basics Approach - page 792

Sequential Search
Perhaps the simplest way to search an array is to loop over the elements of the array
and check each one to see if it is the target number. As we mentioned earlier, this is
called a sequential search because it examines every element in sequence.
We implemented a sequential search of an array of integers in Chapter 7. The code
uses a for loop and is relatively straightforward. The algorithm returns -1 if the loop
completes without finding the target number:

// Sequential search algorithm.
// Returns the index at which the given target number first
// appears in the given input array, or -1 if it is not found.
public static int indexOf(int[] list, int target) {
for (int i = 0; i < list.length; i++) {
if (list[i] == target) {
return i;

}

}
return -1; // not found

}

Using the rules stated in the previous section, we predict that the sequential search
algorithm is a linear O ( N ) algorithm because it contains one loop that traverses at most N
elements in an array. (We say “at most” because if the algorithm finds the target element,
it stops and immediately returns the index.) Next, we'll time it to verify our prediction.
Figure 13.5 shows actual results of running the sequential search algorithm on ran-
domly generated arrays of integers. Searches were conducted for a value known to be
in the array and for a value not in the array.

Runtime
when
element is
found (ms)

Runtime
when
element is
not found (ms)

N

1000
900
800
700
600
500
400
300
200
100
0

100000
200000
400000
800000
1.6e6
3.2e6
6.4e6
1.3e7
2.6e7
5.1e7
1.0e8
2.0e8

0
0
0
0
0
15
16
32
37
45
72
125

0
0
0
0
16
16
31
47
93
203
402
875

Input size (N)

Figure 13.5 Runtimes for sequential search algorithm