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

Rather than trying to further tweak our nested loop solution, let's try to think of a
more efficient algorithm. As we noted earlier, the range of values in an array is the
difference between the array's largest and smallest elements. We don't really need
to examine all pairs of values to find this range; we just need to discover the pair
representing the largest and smallest values. We can discover both of these values in
a single loop over the array by using a min/max loop, discussed in Chapter 4. The
following new algorithm demonstrates this idea:

public static int range3(int[] numbers) {
int max = numbers[0];
int min = max;
for (int i = 1; i < numbers.length; i++) {
if (numbers[i] > max) {
max = numbers[i];
} else if (numbers[i] < min) {
min = numbers[i];

}

}
return max - min;

}

Since this algorithm passes over the array only once, we'd hope that its runtime
would be proportional to the array's length. If the array length doubles, the runtime
should double, not quadruple. Figure 13.4 shows its runtime.

1000
2000
4000
8000
16000
32000
64000
128000
256000
512000
1e6
2e6
4e6
8e6
1.67e7
3.3e7
6.5e7
1.3e8
2.6e8

N Runtime (ms)

0
0
0
0
0
0
0
0
0
0
0
16
31
47
94
188
453
797
1578

1800
1600
1400
1200
1000
800
600
400
200
0

Input size (N)

Figure 13.4

Runtimes for third version of range algorithm