# Find minimum and maximum with minimum number of comparisons

Posted in

Vinay Khatri
Last updated on September 17, 2024

## 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```