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++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
#include <iostream> #include <climits> using namespace std; // Divide & Conquer solution to find minimum and maximum number in an array void findMinAndMax(int arr[], int low, int high, int& min, int& max) { // if array contains only one element if (low == high) // common comparison { if (max < arr[low]) // comparison 1 max = arr[low]; if (min > arr[high]) // comparison 2 min = arr[high]; return; } // if array contains only two elements if (high - low == 1) // common comparison { if (arr[low] < arr[high]) // comparison 1 { if (min > arr[low]) // comparison 2 min = arr[low]; if (max < arr[high]) // comparison 3 max = arr[high]; } else { if (min > arr[high]) // comparison 2 min = arr[high]; if (max < arr[low]) // comparison 3 max = arr[low]; } return; } // find mid element int mid = (low + high) / 2; // recurse for left sub-array findMinAndMax(arr, low, mid, min, max); // recurse for right sub-array findMinAndMax(arr, mid + 1, high, min, max); } // main function int main() { int arr[] = { 7, 2, 9, 3, 1, 6, 7, 8, 4 }; int n = sizeof(arr) / sizeof(arr[0]); // initialize the minimum element by infinity and the // maximum element by minus infinity int max = INT_MIN, min = INT_MAX; findMinAndMax(arr, 0, n - 1, min, max); cout << "The minimum element in the array is " << min << '\n'; cout << "The maximum element in the array is " << max; return 0; } |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
// Create a Pair class to wrap immutable primitive ints class Pair { public int max, min; public Pair(int max, int min) { this.max = max; this.min = min; } } class FindMinMax { // Divide & Conquer solution to find minimum and maximum number in an array public static void findMinAndMax(int[] A, int left, int right, Pair p) { // if array contains only one element if (left == right) // common comparison { if (p.max < A[left]) { // comparison 1 p.max = A[left]; } if (p.min > A[right]) { // comparison 2 p.min = A[right]; } return; } // if array contains only two elements if (right - left == 1) // common comparison { if (A[left] < A[right]) // comparison 1 { if (p.min > A[left]) { // comparison 2 p.min = A[left]; } if (p.max < A[right]) { // comparison 3 p.max = A[right]; } } else { if (p.min > A[right]) { // comparison 2 p.min = A[right]; } if (p.max < A[left]) { // comparison 3 p.max = A[left]; } } return; } // find mid element int mid = (left + right) / 2; // recurse for left sub-array findMinAndMax(A, left, mid, p); // recurse for right sub-array findMinAndMax(A, mid + 1, right, p); } public static void main(String[] args) { int[] A = { 7, 2, 9, 3, 1, 6, 7, 8, 4 }; // initialize the minimum element by infinity and the // maximum element by minus infinity Pair p = new Pair(Integer.MIN_VALUE, Integer.MAX_VALUE); findMinAndMax(A, 0, A.length - 1, p); System.out.println("The minimum element in the array is " + p.min); System.out.println("The maximum element in the array is " + p.max); } } |
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
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.