# Maximum and minimum of an array using minimum number of comparisons

find Maximum and minimum of an array .

**Input:
N = 5
Arr[] = {15, 2, 45, 12, 7}
Output: 45 2
Explanation: as 45 has max value and 2 has min value.**

**method 1:**

take two variables for ma and mi

first let them take the value of a[0]

now start comparing them by running a loop through all the elements in array

int minmax(int a[],int n) { int mi=a[0]; //let min element be a[0] int ma=a[0]; //let max element be a[0] //lets start to compare elements from 1st index for(int i=1;i<n;i++) { if(a[i]<mi) { mi=a[i]; //change the min element if //something smaller than previous min occurs } if(a[i]>ma) { ma=a[i]; //change the max element if //something greater than previous max occurs } } cout<<ma<<" "<<mi; }

**Time Complexity: O(n)**

**METHOD 2:**

**(Compare in Pairs)**

**If n is odd then initialize min and max as first element. If n is even then initialize min and max as minimum and maximum of the first two elements respectively. For rest of the elements, pick them in pairs and compare their maximum and minimum with max and min respectively. **

struct Pairminmax(int arr[], int n) { int i; // If array has even number of elements // then initialize the first two elements // as minimum and maimum if (n % 2 == 0) { if (arr[0] > arr[1]) { ma = arr[0]; mi = arr[1]; } else { mi = arr[0]; ma = arr[1]; } // Set the starting index for loop i = 2; } // If array has odd number of elements // then initialize the first element as // minimum and maimum else { mi = arr[0]; ma = arr[0]; // Set the starting index for loop i = 1; } // In the while loop, pick elements in // pair and compare the pair with ma // and min so far while (i < n - 1) { if (arr[i] > arr[i + 1]) { if(arr[i] > ma) ma = arr[i]; if(arr[i + 1] < mi) mi = arr[i + 1]; } else { if (arr[i + 1] > ma) ma = arr[i + 1]; if (arr[i] < mi) mi = arr[i]; } // Increment the index by 2 as // two elements are processed in loop i += 2; } cout<<ma<<" "mi; }

Time Complexity: O(n)

method 2 is better than method 1

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