Question: Find minimum and maximum in an unsorted array in minimum number of comparisons.

Answer: We can easily find minimum and maximum in single iteration though the input array making 2 comparisons at every step. This will have 2n comparisons and time complexity O(n). Sounds Good?

Yes it does sound good but not as question says “minimum number of comparisons” not time complexity. We will see if we can reduce the number of comparisons.

If we pick 2 elements at a time 1) compare the larger element with max find till now, 2) compare the smaller elements with min find till now and 3) update accordingly, we will be able to mark maximum and in minimum element in 3 comparison for every pair. It means that for an n element array, total number of comparison will be 3n/2.

Code:
void FindMinMax(int input[], int len)
{
   int min, max;
   int i, no_of_comp;
  
   i = no_of_comp = 0;   
   min = INT_MAX; /* Initialize with INT_MAX */
   max = INT_MIN; /* Initialize with INT_MIN */
  
   /* If no of elements in input are odd,
    initialize max and min with first element. */
   if (len%2){
           min = max = input[0];
           i++;
   }

   /* In the while loop, pick elements in pair and
        compare the pair with max and min so far */
   while(i < len-1)
   {
       if(input[i] > input[i+1])
       {
           if(input[i] > max)
               max = input[i];
           if(input[i+1] < min)
               min = input[i+1];
       }
       else
       {
           if(input[i+1] > max)
               max = input[i+1];
           if(input[i] < min)
               min = input[i];
       }
       /* Increase by 2 as 2 elements are processed every time */
       i += 2;
       /* Increase comparison by 3 coz in every iteration of loop,
        3 comparison are made. */
       no_of_comp += 3;
   }                        
   cout << "min = " << min << ", max = " << max << \
   ", Number of comparisons = "    << no_of_comp << endl;
}

Complexity: O(n)

Number of comparisons:
3n/2 (If input length is Even)
3(n-1)/2 (If input length is Odd)

Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.