Maximum and minimum of an array using Linear search
Initialize values of min and max as minimum and maximum of the first two elements respectively. Starting from 3rd, compare each element with max and min, and change max and min accordingly (i.e., if the element is smaller than min then change min, else if the element is greater than max then change max, else ignore the element)
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 n) { struct pair minmax; int i; /*If there is only one element then return it as min and max both*/if (n == 1) { minmax.max = arr[0]; minmax.min = arr[0]; return minmax; } /* If there are more than one elements, then initialize min and max*/if (arr[0] > arr[1]) { minmax.max = arr[0]; minmax.min = arr[1]; } else{ minmax.max = arr[1]; minmax.min = arr[0]; } for (i = 2; i<n; i++) { if (arr[i] > minmax.max) minmax.max = arr[i]; else if (arr[i] < minmax.min) minmax.min = arr[i]; } 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.
In this method, the total number of comparisons is 1 + 2(n-2) in the worst case and 1 + n – 2 in the best case.
In the above implementation, the worst case occurs when elements are sorted in descending order and the best case occurs when elements are sorted in ascending order.
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;
};