Find minimum and maximum with minimum number of comparisons

Problem

Given an array of integers, find the minimum and maximum elements in it with a 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 the 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:

• Print a two-dimensional view of a Binary Tree
• Find a Pair with the given sum in a BST
• Construction of an Expression Tree
• Create a mirror of an m–ary Tree
• Minimum Edit Distance
• The Stock Span Problem
• Diameter of a Binary Tree
• Bottom View of a Binary Tree
• Merge Sort for Linked Lists
• Check if a subarray with 0 sum exists or not