2.8K
In this article, you’ll be learning how you can find the minimum and maximum element of an Array using STL in C++
Given an array arr[], find the minimum and maximum element of this array using STL in C++.
Example:
Input: 1, 11, 2, 4, 19, 22, 34, 56, 71, 23, 2, 0, 53
Output: min = 0, max = 71
Approach 1: Linear Comparisons
- Consider the first element as the minimum and maximum
- From the second element onwards compare each element with the minimum and maximum.
- If the element is less than the minimum, then make it as the new minimum.
- If the element is greater than the maximum, then make it as the new maximum.
- Number of comparisons in worst case: 2(n-1)
#include<bits/stdc++.h>
using namespace std;
class MinMax
{
public:
// Method to find min and max elements of an array using
// Linear comparing
vector<int> minMaxLinearCompare(vector<int> &arr, int size)
{
// 0th index: minimum
// 1st index: maximum
int max_index = 1;
int min_index = 0;
vector<int> minmax;
// input array is empty
if(size == 0) return minmax;
minmax.push_back(arr[0]);
minmax.push_back(arr[0]);
// comparing each element with min and max
for(int i=1; i<size; i++)
{
if(arr[i] > minmax[max_index])
minmax[max_index] = arr[i];
else if(arr[i] < minmax[min_index])
minmax[min_index] = arr[i];
}
return minmax;
}
};
int main()
{
//creating the ReverseAray object
MinMax mnmx;
vector<int> arr = {1,11,2,4,19,22,34,56,71,23,2,0,53};
int arr_size = arr.size();
vector<int> mnmax;
mnmax = mnmx.minMaxLinearCompare(arr, arr_size);
if(mnmax.size() > 0)
{
cout<<"min "<<mnmax[0]<<" max "<<mnmax[1]<<endl;
}
return 0;
}
Approach 2: Pair-wise Comparisons
- If the size of array is odd, then assign first element as minimum and maximum
- If the size of array is even, then compare the first two elements, make the larger element as maximum and smaller element as minimum.
- From the third element onwards consider two elements at a time and compare them, then compare the lager element with maximum and smaller one with the minimum.
- Number of comparisons in worst case: 3/2(n-1) + 1
#include<bits/stdc++.h>
using namespace std;
class MinMax
{
public:
// Method to find min and max elements of an array using
// comparison in pairs
vector<int> minMaxPairCompare(vector<int> &arr, int size)
{
// 0th index: minimum
// 1st index: maximum
int max_index = 1;
int min_index = 0;
int begin_index = -1;
vector<int> minmax;
// input array is empty
if(size == 0) return minmax;
// input array contains only one element
if(size == 1)
{
minmax.push_back(arr[0]);
minmax.push_back(arr[0]);
return minmax;
}
// no. of elements is even
if(size%2 == 0)
{
minmax.push_back(min(arr[0],arr[1]));
minmax.push_back(max(arr[0],arr[1]));
begin_index = 2;
}
else
{
minmax.push_back(arr[0]);
begin_index = 1;
}
// looping through the array considering 2 elements at once
for(int i=begin_index;i<size;i+=2)
{
// comparing max element with maximum b/w ith and (i+1)th element
if(max(arr[i],arr[i+1]) > minmax[max_index])
minmax[max_index] = max(arr[i],arr[i+1]);
// comparing min element with minimum b/w ith and (i+1)th element
if(min(arr[i],arr[i+1]) < minmax[min_index])
minmax[min_index] = min(arr[i],arr[i+1]);
}
return minmax;
}
};
int main()
{
//creating the ReverseAray object
MinMax mnmx;
vector<int> arr = {1,11,2,4,19,22,34,56,71,23,2,0,53};
int arr_size = arr.size();
vector<int> mnmax;
mnmax = mnmx.minMaxPairCompare(arr, arr_size);
if(mnmax.size() > 0)
{
cout<<"min "<<mnmax[0]<<" max "<<mnmax[1]<<endl;
}
return 0;
} 