# Find minimum and maximum with minimum number of comparisons

Posted in

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.

[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