Maximum and minimum of an array by comparing in pairs
If n is odd then initialize min and max as the first element.
If n is even then initialize min and max as minimum and maximum of the first two elements respectively.
For the rest of the elements, pick them in pairs and compare their maximum and minimum with max and min respectively.
Below is the implementation of the above approach:
C
#include<stdio.h> /* structure is used to return two values from minMax() */struct pair { int min; int max; }; struct pair getMinMax(int arr[], int n) { struct pair minmax; int i; /* If array has even number of elements then initialize the first two elements as minimum and maximum */if (n%2 == 0) { if (arr[0] > arr[1]) { minmax.max = arr[0]; minmax.min = arr[1]; } else { minmax.min = arr[0]; minmax.max = arr[1]; } i = 2; /* set the starting index for loop */} /* If array has odd number of elements then initialize the first element as minimum and maximum */else{ minmax.min = arr[0]; minmax.max = arr[0]; i = 1; /* set the starting index for loop */} /* In the while loop, pick elements in pair and compare the pair with max and min so far */while (i < n-1) { if (arr[i] > arr[i+1]) { if(arr[i] > minmax.max) minmax.max = arr[i]; if(arr[i+1] < minmax.min) minmax.min = arr[i+1]; } else { if (arr[i+1] > minmax.max) minmax.max = arr[i+1]; if (arr[i] < minmax.min) minmax.min = arr[i]; } i += 2; /* Increment the index by 2 as two elements are processed in loop */} 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, arr_size); printf("nMinimum element is %d", minmax.min); printf("nMaximum element is %d", minmax.max); getchar(); } |
Output:
Minimum element is 1 Maximum element is 3000
Time Complexity: O(n)
Auxiliary Space: O(1) as no extra space was needed.
Total number of comparisons: Different for even and odd n, see below:
If n is odd: 3*(n-1)/2
If n is even: 1 Initial comparison for initializing min and max,
and 3(n-2)/2 comparisons for rest of the elements
= 1 + 3*(n-2)/2 = 3n/2 -2
Second and third approaches make the equal number of comparisons when n is a power of 2.
In general, method 3 seems to be the best.
Please write comments if you find any bug in the above programs/algorithms or a better way to solve the same problem.
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;
};