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]


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.


Download   Run Code


Download   Run Code


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.

1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)


Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

Leave a Reply

newest oldest most voted
Notify of

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.