Find minimum and maximum with minimum number of comparisons

Posted in

Find minimum and maximum with minimum number of comparisons

Vinay Khatri
Last updated on June 10, 2022

    Problem

    Given an array of integers, find minimum and maximum elements in it with minimum number of comparisons.

    Sample Input

    [1, 3, 2, 7]

    Sample Output

    Minimum element is 1
    Maximum element is 7
    

    Brute Force Approach

    We can search for the required elements by comparing each element and finally returning the result. This will make 3( n -1) comparisons in the worst case. The time complexity of the approach is O(N).

    Efficient Approach

    We can compare the elements in pairs and find the required result. Following is the algorithm for it. If size of the array is odd then initialize minimum and maximum variables as the first element. If size is even then initialize minimum and maximum 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 maximum and minimum respectively.

    C Programming

    #include<stdio.h>
    int minimum = 100000;
    int maximum = -1;
    void solve(int arr[], int n)
    {   
    int i;
    
    if (n%2 == 0)
    {       
        if (arr[0] > arr[1])    
        {
        maximum = arr[0];
        minimum = arr[1];
        }
        else
        {
        minimum = arr[0];
        maximum = arr[1];
        }
        i = 2; 
    }
    
    else
    {
        minimum = arr[0];
        maximum = arr[0];
        i = 1;
    }
    
    while (i < n-1) 
    { 
        if (arr[i] > arr[i+1])      
        {
        if(arr[i] > maximum)    
            maximum = arr[i];
        if(arr[i+1] < minimum) 
            minimum = arr[i+1]; 
        } 
        else { if (arr[i+1] > maximum) 
            maximum = arr[i+1];
        if (arr[i] < minimum)       
            minimum = arr[i];   
        }   
        i += 2; 
    }       
    }
    
    void main()
    {
    int arr[] = {1, 3, 2, 7};
    int n = sizeof(arr)/sizeof(arr[0]);
    solve (arr, n);
    printf("Minimum element is %d\n", minimum);
    printf("Maximum element is %d", maximum);
    }

    Output

    Minimum element is 1
    Maximum element is 7
    

    C++ Programming

    #include<bits/stdc++.h>
    using namespace std;
    int minimum = 100000;
    int maximum = -1;
    void solve(int arr[], int n)
    {	
    int i;
    
    if (n%2 == 0)
    {		
    	if (arr[0] > arr[1])	
    	{
    	maximum = arr[0];
    	minimum = arr[1];
    	}
    	else
    	{
    	minimum = arr[0];
    	maximum = arr[1];
    	}
    	i = 2; 
    }
    else
    {
    	minimum = arr[0];
    	maximum = arr[0];
    	i = 1;
    }
    while (i < n-1) 
    { 
            if (arr[i] > arr[i+1])		
    	{
    	if(arr[i] > maximum)	
    		maximum = arr[i];
    	if(arr[i+1] < minimum) 
                    minimum = arr[i+1]; 
            } 
            else 
            { 
             if (arr[i+1] > maximum)	
    		maximum = arr[i+1];
    	if (arr[i] < minimum)		
    		minimum = arr[i];	
    	}	
    	i += 2; 
    }		
    }
    int main()
    {
    int arr[] = {1, 3, 2, 7};
    int n = sizeof(arr)/sizeof(arr[0]);
    solve (arr, n);
    cout<<"Minimum element is "<<minimum<<"\n";
    cout<<"Maximum element is "<<maximum;
    }
    

    Output

    Minimum element is 1
    Maximum element is 7
    

    Python Programming

    def solve(arr):
    	
    	n = len(arr)
    
    	if(n % 2 == 0):
    		maximum = max(arr[0], arr[1])
    		minimum = min(arr[0], arr[1])
    		
    		i = 2
    		
    	else:
    		maximum = minimum = arr[0]
    		
    		i = 1
    		
    	while(i < n - 1):
    		if arr[i] < arr[i + 1]:
    			maximum = max(maximum, arr[i + 1])
    			minimum = min(minimum, arr[i])
    		else:
    			maximum = max(maximum, arr[i])
    			minimum = min(minimum, arr[i + 1])
    			
    		i += 2
    	
    	return (maximum, minimum)
    	
    arr = [1, 3, 2, 7]
    maximum, minimum = solve(arr)
    print("Minimum element is", minimum)
    print("Maximum element is", maximum)
    

    Output

    Minimum element is 1
    Maximum element is 7

    People are also reading:

    Leave a Comment on this Post

    0 Comments