Searching and Sorting: Maximum and minimum of an array using minimum number of comparisons

Problem Statement:

You are given an unsorted array, you need to get the maximum and minimum element of the array using minimum comparisons.

Solution

There are multiple ways to solve this problem:

1. Linear search:

Here we simply search the whole array and update minimum and maximum values accordingly.

But here the number of comparisons: 1 + 2(n-2)

2. Efficient Method is by comparing in pairs:

Here we compare in pairs to arrive at the solution.

First we should get the size of the array.
If the array size is odd, then initialize min and max as first element.
If the array size is even, then initialize min and max as first two element respectively.

Then for the next elements, pick them in pairs and start comparing.

If n is odd the comparisons required are 3*(n-1)/2
If n is even the comparisons required are 3n/2 -2

Solution in C++

#include <vector>    
#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <unordered_map>
#include <vector>
#include <sstream> 

using namespace std;

void get_min_max(int arr[], int n) 
{ 
    int min;
    int max;
    int i; 
     
    // if array is even then take first 
    // 2 elements are min and max
    if (n % 2 == 0) 
    { 
        if (arr[0] > arr[1])     
        { 
            max = arr[0]; 
            min = arr[1]; 
        } 
        else
        { 
            min = arr[0]; 
            max = arr[1]; 
        } 
         
        // as we have already choose 2 elements,
        // array index should start from 2
        i = 2; 
    } 
    // if odd 
    else
    { 
        min = arr[0]; 
        max = arr[0]; 
         
        i = 1; 
    } 
     

    while (i < n - 1) 
    {         
        if (arr[i] > arr[i + 1])         
        { 
            if(arr[i] > max)     
                max = arr[i]; 
                 
            if(arr[i + 1] < min)         
                min = arr[i + 1];     
        } 
        else       
        { 
            if (arr[i + 1] > max)     
                max = arr[i + 1]; 
                 
            if (arr[i] < min)         
                min = arr[i];     
        } 

        i += 2; 
    } 

        cout << "The min element is " << min << " and max "
            "element is " << max << endl;  
} 

int main() 
{ 
    int arr[] = { 3, 5, 1, 2, 8, 9 }; 
    int arr_size = 6; 
     
    get_min_max(arr, arr_size); 
     

    return 0; 
}  

 

Output:

The min element is 1 and max element is 9
Write a Comment

Leave a Comment

Your email address will not be published. Required fields are marked *