Problem : Given an array of integers find the max. and min. using minimum comparisons.
Solution
Method 1 (Naive) - Iterate through the array, and update min and max pointers
1\. Iterate through the array, select element a
2\. Update min by comparing (min, a)
3\. Update max by comparing (max, a)
Number of comparison here will be ~2N, if N is number of element.
Time complexity will be O(n) though.
Method 2 - Pick 2 elements at time, compare them and compare them with corresponding min and max
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.(Actually it is 3N/2 if N is even, and 3(N-1)/2 if N is odd)
Example
Consider
A = [a1, a2, a3, a4, a5]
Compare a1 & a2 and calculate min12, max12:
if (a1 > a2)
min12 = a2
max12 = a1
else
min12 = a1
max12 = a2
```Similarly calculate `min34`, `max34`. Since `a5` is alone, keep it as it is...
This way you would do 3 comparisons for 2 elements, amounting to `3N/2` total comparisons for `N` elements.
**Iterative solution**
class Pair
{
public int min;
public int max;
}
public Pair getMinMax(int arr[], int n)
{
Pair minmax;
int i;
// If array has even number of elements then
// initialize the first two elements as minimum and
// maximum
if (n%2 == 0)
{
if (arr[0] > arr[1])
{
minmax.max = arr[0];
minmax.min = arr[1];
}
else
{
minmax.min = arr[0];
minmax.max = arr[1];
}
i = 2; // set the startung index for loop
}
// If array has odd number of elements then
// initialize the first element as minimum and
// maximum
else
{
minmax.min = arr[0];
minmax.max = arr[0];
i = 1; // set the startung index for loop
}
// In the while loop, pick elements in pair and
// compare the pair with max and min so far
while (i < n-1)
{
if (arr[i] > arr[i+1])
{
if(arr[i] > minmax.max)
minmax.max = arr[i];
if(arr[i+1] < minmax.min)
minmax.min = arr[i+1];
}
else
{
if (arr[i+1] > minmax.max)
minmax.max = arr[i+1];
if (arr[i] < minmax.min)
minmax.min = arr[i];
}
i += 2; //Increment the index by 2 as two
// elements are processed in loop
}
return minmax;
}
**Method 3 - Tournament Method**
This is similar to previous method, where we were taking 2 elements at a time. Here we are doing this in local subarray recursively and returning elements accordingly.
Pair MaxMin(array, array_size)
if array_size = 1
return element as both max and min
else if arry_size = 2
one comparison to determine max and min
return that pair
else // array_size > 2
recur for max and min of left half
recur for max and min of right half
one comparison determines true max of the two candidates
one comparison determines true min of the two candidates
return the pair of max and min
Here is the code
void minmax (int[] a, int left, int right, int min, int max) {
int lmin, lmax, rmin, rmax, mid;
if (left==right) {
min = a[left];
max = a[right];
} else if (right == left+ 1) {
if (a[left] > a[right]) {
min = a[right];
max = a[left];
} else {
min = a[left];
max = a[right];
}
} else {
mid = (left+right) / 2;
minmax(a,left, mid, lmin, lmax);
minmax(a, mid + 1,right, rmin, rmax);
min = (lmin > rmin) ? rmin : lmin;
max = (lmax > rmax) ? lmax : rmax;
}
}
Thanks.
References -[stackoverflow](http://stackoverflow.com/questions/13544476/how-to-find-max-and-min-in-array-using-minimum-comparisons) , [geeksforgeeks](http://www.geeksforgeeks.org/maximum-and-minimum-in-an-array/)