Find Minimum and Maximum element in an array by doing minimum comparisons

Given an array of integers, find minimum and maximum element present in it by doing minimum comparisons.

 


For example,


Input: arr = [5, 7, 2, 4, 9, 6]

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

 


 

We can easily solve this problem by using Divide & Conquer. The idea is to recursively divide the array into two equal parts and update the maximum and minimum of the whole array in recursion itself by passing minimum and maximum variables by reference. The base conditions for the recursion will be when sub-array is of length 1 or 2. All the comparisons will be handled efficiently in base conditions.

C++

Download   Run Code

Output:

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

Performance –

The recurrence relation for above solution can be defined as –

T(n) = 2T(n/2) + 2 when n > 2
T(n) = 5 when n = 2
T(n) = 3 when n = 1

Solving above recurrence, we get –

T(n) = (3n)/2 + 2n + 1      // If the array has even number of elements
T(n) = (3(n-1))/2 + 2n + 1  // If the array has odd number of elements

The validity of above relation can be tested here.
 

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 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz