Maximum and minimum of an array using minimum number of comparisons

 

find Maximum and minimum of an array .

Input: 
N = 5
Arr[] = {15, 2, 45, 12, 7}
Output: 45 2
Explanation: as 45 has max value and 2 has min value.

method 1:

Simple Linear Search:

take two variables for ma and mi 
first let them take the value of a[0]
now start comparing them by running a loop through all the elements in array

keep changing the value of ma and mi if value greater than or smaller than are found respectively.

int minmax(int a[],int n)
{  
   int mi=a[0]; //let min element be a[0]
   int ma=a[0]; //let max element be a[0]

//lets start to compare elements from 1st index
   for(int i=1;i<n;i++)
   {
    
     if(a[i]<mi)
     {
       mi=a[i]; //change the min element if  
                //something smaller than previous min occurs
     }

     if(a[i]>ma)
     {
       ma=a[i]; //change the max element if  
                //something greater than previous max occurs
     }

   }
   cout<<ma<<" "<<mi;

}

Time Complexity: O(n)

METHOD 2:

(Compare in Pairs) 

If n is odd then initialize min and max as first element. 
If n is even then initialize min and max as minimum and maximum of the first two elements respectively. 
For rest of the elements, pick them in pairs and compare their 
maximum and minimum with max and min respectively. 

struct Pairminmax(int arr[], int n) 
{    
    int i; 
     
    // If array has even number of elements 
    // then initialize the first two elements 
    // as minimum and maimum 
    if (n % 2 == 0) 
    { 
        if (arr[0] > arr[1])     
        { 
            ma = arr[0]; 
            mi = arr[1]; 
        } 
        else
        { 
            mi = arr[0]; 
            ma = arr[1]; 
        } 
         
        // Set the starting index for loop 
        i = 2; 
    } 
     
    // If array has odd number of elements 
    // then initialize the first element as 
    // minimum and maimum 
    else
    { 
        mi = arr[0]; 
        ma = arr[0]; 
         
        // Set the starting index for loop 
        i = 1; 
    } 
     
    // In the while loop, pick elements in 
    // pair and compare the pair with ma 
    // and min so far 
    while (i < n - 1) 
    {         
        if (arr[i] > arr[i + 1])         
        { 
            if(arr[i] > ma)     
                ma = arr[i]; 
                 
            if(arr[i + 1] < mi)         
                mi = arr[i + 1];     
        } 
        else       
        { 
            if (arr[i + 1] > ma)     
                ma = arr[i + 1]; 
                 
            if (arr[i] < mi)         
                mi = arr[i];     
        } 
         
        // Increment the index by 2 as 
        // two elements are processed in loop 
        i += 2; 
    }         
    cout<<ma<<" "mi; 
} 

Time Complexity: O(n)

method 2 is better than method 1

       If n is odd:    3*(n-1)/2  

       If n is even:   1 Initial comparison for initializing min and max, 

                           and 3(n-2)/2 comparisons for rest of the elements  

                      =  1 + 3*(n-2)/2 = 3n/2 -2