Find Minimum and Maximum element in an array using minimum comparisons

Given an array of integers, find out minimum and maximum element present using minimum comparisons.


For example,

Input: A[] = [5, 7, 2, 4, 9, 6]
Output:
The minimum element in the array is 2
The maximum element in the array is 9

 


 

Naive solution would be to compare each element of the array for minimum and maximum element by considering ONE element at a time. The time complexity of this solution would be linear.

 
C++ implementation –
 

Download   Run Code

Output:

The minimum element in the array is 2
The maximum element in the array is 9

 
Performance –

Above solution does 2(n-1) comparisons in best case and 3(n-1) comparisons in worst case. The worst case happens when all elements in the array are equal or they are sorted in descending order. Best case happens when the input is sorted in ascending order. (Note that we have also considered n-1 comparisons done by for loop).
 

Can we do better?

We can improve comparisons done by above solution by considering TWO elements at a time (i.e. consider elements in pairs). One special case we need to handle separately when array has odd number of elements.

 
C++ implementation –
 

Download   Run Code

Output:

The minimum element in the array is 2
The maximum element in the array is 9

 
Performance –

If the array has even number of elements n, then above solution does n/2 + 3n/2 + 2 comparisons in both best and worst case. (Note that we have also considered n/2 comparisons done by for loop).

If the array has odd number of elements n, then above solution does (n-1)/2 + 3(n-1)/2 + 4 comparisons in both best and worst case. (We have also considered (n-1)/2 comparisons done by for loop).

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂