When gathering statistics on a set of values, min and max are natural inclusions. Both are simple to locate by iterating over the set of values, performing \(n-1\) (where \(n\) is the size of the set) comparisons. Locating both seems trivial – perform each for a total cost of \(2n\). However, there is a more efficient method for locating both minimum and maximum values simultaneously. Here, we discuss such an algorithm that reduces the individual element approach of \(2n\) to approximately \(1.5n\).
Simultaneous Min/Max
The premise is quite simple; review the data in pairs. By doing so, we need only \(\frac{n}{2}\) iterations and three comparisons: value 1 (\(v1\)) to value 2 (\(v2\)), \(\max(v1,v2)\) to max, and \(\min(v1,v2)\) to min – note: we do not compute min and max here, they are the result of the first comparison. This reduces the number of comparisons from \(2n\) to approximately \(\frac{3}{2}n=1.5n\). I say approximately because it depends on the number of elements in the set.
If \(n\) is even (i.e., \(n%2==0\)), the number of comparisons is \(\frac{3\left(n-2\right)}{2}+1\), if odd \(3\left\lfloor \frac{n}{2}\right\rfloor \). Thus, approximately \(1.5n\).
/**
* This class examines an efficient method of locating both minimum and
* maximum values in a set (an array for this example). The method discussed
* is more efficient than the naive approach of computing min and max for
* each value individually, which requires \(2n\) comparisons versus
* approximately \(1.5n\) herein; where \(n\) is the size of the set.
* @author Ray Hylock
*/
public class SimultaneousMinMax {
/**
* Computes min and max simultaneously. This is done by looking at each
* pair instead of individual element. If {@code |values|} is even, the
* number of comparisons is \(\frac{3\left(n-2\right)}{2}+1\), if odd
* \(3\left\lfloor \frac{n}{2}\right\rfloor \), where \(n\) is the size
* of the array {@code values} (i.e., \(n=|values|\). Thus, the approximate
* runtime is \(1.5n\).
* @param values the array of values
* @return a 2D array: 0 = min and 1 = max
*/
public static int[] minMax(int[] values){
int length = values.length, start;
int min, max, v1, v2; // the data type here changes based on input
// if even, then we look at the first pair
if(length % 2 == 0){
v1 = values[0];
v2 = values[1];
if(v1 > v2){
max = v1;
min = v2;
} else {
min = v1;
max = v2;
}
start = 2;
// if odd, set min/max to first element to allow for pair iterating
} else {
min = max = values[0];
start = 1;
}
// iterate over each pair
for(int i=start; i<length; i+=2){
v1 = values[i];
v2 = values[i+1];
if(v1 > v2){
if(v1 > max) max = v1;
if(v2 < min) min = v2;
} else {
if(v1 < min) min = v1;
if(v2 > max) max = v2;
}
}
// return {min, max}
return new int[]{min, max};
}
}Example usage of this class is as follows:
public class SimultaneousMinMaxTest {
public static void main(String[] args) {
int[] values = {-1,11,2,3,4,5,6,7,8,9,10,0,12,-12};
int[] minMax = SimultaneousMinMax.minMax(values);
System.out.println(String.format("min: %d, max: %d", minMax[0], minMax[1]));
}
}The output from this example is:
min: -12, max; 12