Maximum and minimum of an array using minimum number of comparisons

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 :
A[]={4,2,-1,5,0,-5,7,3,6}
Output :
Min Element -5
Max Element 7

Input :
A[]={3,8,4,2,6,9}
Output :
Min Element 2
Max Element 9

Approach:
The idea is to use the Two Pointer Approach, so that we can minimize the number of comparisons.

Below is the Step by Step Approach to Solve the Problem:

1. Create two variables say mn ,mx for storing the minimum and maximum element respectively.
2. Initialize mn and mx with first element of Array.
3. Create two variables l and r initialize them with 0 and n-1 respectively
4. Traverse the Array till l is less than or equal to r.
5. while Traversing the Array Check
   1. If element at lth position is less than or equal to element at rth position in the Array
      1. Make mn equal to minimum of mn and element present at lth position in the Array.
      2. Make mx equal to maximum of mx and element present at rth position in the Array.
   2. Otherwise
      1. Make mn equal to minimum of mn and element present at rth position in the Array
      2. Make mx equal to maximum of mx and element present at lth position in the Array
   3. Increase l by one and Decrease r by one
6. Print the Maximum and Minimum Elements obtained after the loop gets terminated.

Below is implementation of above Approach:

#include <bits/stdc++.h>
using namespace std;

void Min_And_Max(int a[], int n)
{ // Create mn,mx for storing
    // mimimum and maximum
    // element respectively
    int mn, mx;

    // Intitialize mn and mx
    // with a[0]
    mn = a[0];
    mx = a[0];

    // create two variables l and r
    // initilize them
    // with 0 and n-1
    // respectively
    int l = 0, r = n - 1;

    // Traverse Array
    // untill l<=r
    while (l <= r) {
        // if element at lth position
        // is less than or equal to
        // element at rth position
        // in the Array
        if (a[l] <= a[r]) {
            mn = min(mn, a[l]);
            mx = max(mx, a[r]);

        } // otherwise
        else {

            mn = min(mn, a[r]);
            mx = max(mx, a[l]);
        }
        // increase l and r by one
        l++;
        r--;
    }
    // Print Minimum and maximum element
    cout << "Min Element " << mn << endl;
    cout << "Max Element " << mx;
}

// Driver Code
int main()
{

    int a[] = { 4, 2, -1, 5, 0, -5, 7, 3 };

    int n = sizeof(a) / sizeof(a[0]);

    Min_And_Max(a, n);

    return 0;
}

Output:

Min Element -5
Max Element 7 

Time Complexity : O(N)
Space Complexity : O(1)