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 by using divide and conquer technique.

 

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 and conquer (D&C). 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

Java

Download   Run Code

Output:

The minimum element in the array is 1
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

avatar
  Subscribe  
newest oldest most voted
Notify of
Rnet
Guest

This is an inefficient solution. A simple linear search will yield better performance.

Do a linear search, if the new min is found, then no need to do a max comparison. If no new min is found, compare to see if value is max.

So comparisons at each step can be 1 or 2. Even the worst case (reverse sorted) has lesser comparisons than the above method.