Maximum and minimum of an array using the tournament method
Divide the array into two parts and compare the maximums and minimums of the two parts to get the maximum and the minimum of the whole array.
Pair MaxMin(array, array_size)
if array_size = 1
return element as both max and min
else if arry_size = 2
one comparison to determine max and min
return that pair
else /* array_size > 2 */
recur for max and min of left half
recur for max and min of right half
one comparison determines true max of the two candidates
one comparison determines true min of the two candidates
return the pair of max and min
Below is the implementation of the above approach:
C
/* structure is used to return two values from minMax() */#include <stdio.h> struct pair { int min; int max; }; struct pair getMinMax(int arr[], int low, int high) { struct pair minmax, mml, mmr; int mid; // If there is only one element if (low == high) { minmax.max = arr[low]; minmax.min = arr[low]; return minmax; } /* If there are two elements */ if (high == low + 1) { if (arr[low] > arr[high]) { minmax.max = arr[low]; minmax.min = arr[high]; } else { minmax.max = arr[high]; minmax.min = arr[low]; } return minmax; } /* If there are more than 2 elements */ mid = (low + high) / 2; mml = getMinMax(arr, low, mid); mmr = getMinMax(arr, mid + 1, high); /* compare minimums of two parts*/ if (mml.min < mmr.min) minmax.min = mml.min; else minmax.min = mmr.min; /* compare maximums of two parts*/ if (mml.max > mmr.max) minmax.max = mml.max; else minmax.max = mmr.max; return minmax; } /* Driver program to test above function */int main() { int arr[] = { 1000, 11, 445, 1, 330, 3000 }; int arr_size = 6; struct pair minmax = getMinMax(arr, 0, arr_size - 1); printf("nMinimum element is %d", minmax.min); printf("nMaximum element is %d", minmax.max); getchar(); } |
Minimum element is 1 Maximum element is 3000
Time Complexity: O(n)
Auxiliary Space: O(log n) as the stack space will be filled for the maximum height of the tree formed during recursive calls same as a binary tree.
Total number of comparisons: let the number of comparisons be T(n). T(n) can be written as follows:
Algorithmic Paradigm: Divide and Conquer
T(n) = T(floor(n/2)) + T(ceil(n/2)) + 2 T(2) = 1 T(1) = 0
If n is a power of 2, then we can write T(n) as:
T(n) = 2T(n/2) + 2
After solving the above recursion, we get
T(n) = 3n/2 -2
Thus, the approach does 3n/2 -2 comparisons if n is a power of 2. And it does more than 3n/2 -2 comparisons if n is not a power of 2.
C Program For Maximum and Minimum of an Array
Given an array of size N. The task is to find the maximum and the minimum element of the array using the minimum number of comparisons.
Examples:
Input: arr[] = {3, 5, 4, 1, 9}
Output: Minimum element is: 1
Maximum element is: 9Input: arr[] = {22, 14, 8, 17, 35, 3}
Output: Minimum element is: 3
Maximum element is: 35
First of all, how do we return multiple values from a function? We can do it either using structures or pointers.
We have created a structure named pair (which contains min and max) to return multiple values.
struct pair {
int min;
int max;
};