How to find max. and min. in array using minimum comparisons?

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 , geeksforgeeks