How to find max. and min. in array using minimum comparisons?
1. Pick 2 elements(a, b), compare them. (say a > b)2. Update min by comparing (min, b)3. Update max by comparing (max, a)
This way you would do 3 comparisons for 2 elements, amounting to 3N/2
total comparisons for N
elements.
Trying to improve on the answer by srbh.kmr. Say we have the sequence:
A = [a1, a2, a3, a4, a5]
Compare a1
& a2
and calculate min12
, max12
:
if (a1 > a2) min12 = a2 max12 = a1else min12 = a1 max12 = a2
Similarly calculate min34
, max34
. Since a5
is alone, keep it as it is...
Now compare min12
& min34
and calculate min14
, similarly calculate max14
. Finally compare min14
& a5
to calculate min15
. Similarly calculate max15
.
Altogether it's only 6 comparisons!
This solution can be extended to an array of arbitrary length. Probably can be implemented by a similar approach to merge-sort (break the array in half and calculate min
max
for each half).
UPDATE: Here's the recursive code in C:
#include <stdio.h>void minmax (int* a, int i, int j, int* min, int* max) { int lmin, lmax, rmin, rmax, mid; if (i == j) { *min = a[i]; *max = a[j]; } else if (j == i + 1) { if (a[i] > a[j]) { *min = a[j]; *max = a[i]; } else { *min = a[i]; *max = a[j]; } } else { mid = (i + j) / 2; minmax(a, i, mid, &lmin, &lmax); minmax(a, mid + 1, j, &rmin, &rmax); *min = (lmin > rmin) ? rmin : lmin; *max = (lmax > rmax) ? lmax : rmax; }}void main () { int a [] = {3, 4, 2, 6, 8, 1, 9, 12, 15, 11}; int min, max; minmax (a, 0, 9, &min, &max); printf ("Min : %d, Max: %d\n", min, max);}
Now I cannot make out the exact number of comparisons in terms of N
(the number of elements in the array). But it's hard to see how one can go below this many comparisons.
UPDATE: We can work out the number of comparisons like below:
At the bottom of this tree of computations, we form pairs of integers from the original array. So we have N / 2
leaf nodes. For each of these leaf nodes we do exactly 1 comparison.
By referring to the properties of a perfect-binary-tree, we have:
leaf nodes (L) = N / 2 // knowntotal nodes (n) = 2L - 1 = N - 1internal nodes = n - L = N / 2 - 1
For each internal node we do 2 comparisons. Therefore, we have N - 2
comparisons. Along with the N / 2
comparisons at the leaf nodes, we have (3N / 2) - 2
total comparisons.
So, may be this is the solution srbh.kmr implied in his answer.
A somewhat different approach, which uses integer arithmetic instead of comparisons (which wasn't explicitly prohibited)
for(int i=0;i<N;i++) { xmin += x[i]-xmin & x[i]-xmin>>31; xmax += x[i]-xmax & xmax-x[i]>>31;}