Find the Maximum and minimum of an array

Question:

Given an array, find the Max and Min of the array, with less number of comparisons.

Example:

Input : {5, 4, 3, 2, 1}

Max element = 5

Min element = 1

Solution:

We can solve this problem by different ways, some of them are explained in this article are:

1. Iterative Method

2. Tournament Method

 

Method 1. Iterative Method

In this method, we take a for loop and check the elements one by one.
We take 2 variables, that will store the Min and Max values.

Here the time complexity is O(n).

And the number of comparison are 2(n-1).

Because at every step we are comparing 2 times for (n-1) number of times.

Solution in C++

#include <vector>    
#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
  
using namespace std;  
    
int main() 
{      
   vector <int> v = {1, 2, 3, 4, 5};
   int min = v[0];
   int max = v[0];    

   for(int i = 0; i < v.size() ; i++){

      if( v[i] < min){
         min = v[i];
      }

      if(v[i] > max) {
         max = v[i];
      }

   }  

   cout<<"The Max value is = "<< max<<endl; 
   cout<<"The Min value is = "<< min<<endl; 

   return 0;  
} 

Output:

The Max value is = 5
The Min value is = 0

Method 2. Tournament Method

This is a divide and conquer approach.

We shall see in detail how to understand and implement Tournament Method.

In this method, we divide the array into left part and right part recursively till we have 2 elements.

Then we compare those 2 elements to get the maximum and minimum.

Consider the array: {1, 2, 3, 6, 5, 4, 7, 9}

Below we can represent the tournament tree, where each stage represents the minimum of the 2 elements.

Note: Read the tree from bottom up.

Tournament_method

From the image above, we can see that to find the minimum element, we need (n-1) comparisons.

Similarly to find the largest element, we need (n-1) comparisons.

So total will be 2(n-1) comparisons.

It can be further optimized in the last level of the tree.

We can see that it is making n/2 comparison to find both maximum and minimum element.

We can do this step only once for both, hence (n/2) comparisons will be less.

So 2(n -1) – (n/2) = (2n-2) – (n/2) = 3n/2 -2

Solution in C++

In the solution we need to take a pair, that will hold min and max elements.

We create a recursive function to divide the array into left and right part.

Base cases:

1. If there is only 1 element, fill min, max as the same element.

2. If there are only 2 elements, compare and fill min, max elements.

#include <vector>    
#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
  
using namespace std;  

struct Pair 
{
    int min;
    int max;
};

struct Pair find_min_max(int arr[], int start, int end)
{
    struct Pair min_max, min_max_left, min_max_right;     
    int mid;
     
    // If there is only one element 
    if (start == end)
    {
        min_max.max = arr[start];
        min_max.min = arr[start];     
        return min_max;
    } 
     
    // If there are two elements 
    if (end == start + 1)
    { 
        if (arr[start] > arr[end]) 
        {
            min_max.max = arr[start];
            min_max.min = arr[end];
        } 
        else
        {
            min_max.max = arr[end];
            min_max.min = arr[start];
        } 
        return min_max;
    }
     
    // Divide the array, if there are more than 2 elements 
    mid = (start + end) / 2; 
    min_max_left = find_min_max(arr, start, mid);
    min_max_right = find_min_max(arr, mid + 1, end); 
     
    // Now compare minimums of two parts
    if (min_max_left.min < min_max_right.min)
        min_max.min = min_max_left.min;
    else
        min_max.min = min_max_right.min;     
     
    // Now compare maximums of two parts
    if (min_max_left.max > min_max_right.max)
        min_max.max = min_max_left.max;
    else
        min_max.max = min_max_right.max;     
     
    return min_max;
}
 

int main() 
{      
   int arr[] = {1, 2, 3, 4, 5};
   
   struct Pair min_max = find_min_max(arr, 0, 4);

   cout<<"The Max is "<< min_max.max<<endl;
   cout<<"The Min is "<< min_max.min<<endl;

   return 0;  
} 

Output:

The Max is 5
The Min is 1

 

Write a Comment

Leave a Comment

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