Open In App

Maximum and minimum of an array using minimum number of comparisons

Last Updated : 23 May, 2024
Improve
Improve
Like Article
Like
Save
Share
Report

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: 9

Input: arr[] = {22, 14, 8, 17, 35, 3}
Output:  Minimum element is: 3
              Maximum element is: 35

Recommended Practice
Max Min
Try It!
 

Maximum and minimum of an array :

To solve the problem of finding the minimum and maximum elements in an array, you can follow these steps:

Step 1: Write functions to find the minimum (setmini) and maximum (setmaxi) values in the array.

Step 2: In the setmini function:

  • Initialize a variable (mini) to INT_MAX.
  • Iterate through the array, and if an element is smaller than the current mini, update mini to that element.
  • Return the final value of mini.

Step 3: In the setmaxi function:

  • Initialize a variable (maxi) to INT_MIN.
  • Iterate through the array, and if an element is larger than the current maxi, update maxi to that element.
  • Return the final value of maxi.

Step 4: In the main function:

  • Declare an array and its size.
  • Print the result ,Call the setminimum and setmaxi functions to find the minimum and maximum values.

Below is the implementation of the above approach:

C++ 
#include <iostream>
#include <limits.h>
using namespace std;

int setmini(int A[], int N)
{
    int mini = INT_MAX;
    for (int i = 0; i < N; i++) {
        if (A[i] < mini) {
            mini = A[i];
        }
    }
    return mini;
}
int setmaxi(int A[], int N)
{
    int maxi = INT_MIN;

    for (int i = 0; i < N; i++) {
        if (A[i] > maxi) {
            maxi = A[i];
        }
    }
    return maxi;
}
int main()
{
    int A[] = { 4, 9, 6, 5, 2, 3 };
    int N = 6;
    cout <<"Minimum element is: " <<setmini(A, N) << endl;
    cout <<"Miximum  element is: "<< setmaxi(A, N) << endl;
}
Java 
import java.util.Arrays;

public class MinMaxFinder {

    /**
     * Finds the minimum element in an array of integers.
     *
     * @param A The input array.
     * @param N The size of the array.
     * @return The minimum element in the array.
     */
    public static int setmini(int[] A, int N)
    {
        int mini = Integer.MAX_VALUE;
        for (int i = 0; i < N; i++) {
            if (A[i] < mini) {
                mini = A[i];
            }
        }
        return mini;
    }

    /**
     * Finds the maximum element in an array of integers.
     *
     * @param A The input array.
     * @param N The size of the array.
     * @return The maximum element in the array.
     */
    public static int setmaxi(int[] A, int N)
    {
        int maxi = Integer.MIN_VALUE;

        for (int i = 0; i < N; i++) {
            if (A[i] > maxi) {
                maxi = A[i];
            }
        }
        return maxi;
    }

    public static void main(String[] args)
    {
        int[] A = { 4, 9, 6, 5, 2, 3 };
        int N = A.length;
        System.out.println("Minimum element is: "
                           + setmini(A, N));
        System.out.println("Maximum element is: "
                           + setmaxi(A, N));
    }
}
Python 
# Python program to find Maximum and minimum of an array using minimum number of comparisons
def set_min(A):
    mini = float('inf')  # Initialize mini as positive infinity
    for num in A:
        if num < mini:
            mini = num
    return mini

def set_max(A):
    maxi = float('-inf')  # Initialize maxi as negative infinity
    for num in A:
        if num > maxi:
            maxi = num
    return maxi

# Driver code
if __name__ == "__main__":
    A = [4, 9, 6, 5, 2, 3]
    N = len(A)
    print("Minimum element is:", set_min(A))
    print("Maximum element is:", set_max(A))
JavaScript 
// JavaScript code to find the minimum and maximum elements in an array

function setMini(A) {
    let mini = Infinity;
    for (let i = 0; i < A.length; i++) {
        if (A[i] < mini) {
            mini = A[i];
        }
    }
    return mini;
}

function setMaxi(A) {
    let maxi = -Infinity;

    for (let i = 0; i < A.length; i++) {
        if (A[i] > maxi) {
            maxi = A[i];
        }
    }
    return maxi;
}

function main() {
    const A = [4, 9, 6, 5, 2, 3];
    console.log("Minimum element is: " + setMini(A));
    console.log("Maximum element is: " + setMaxi(A));
}

main();
//This code is contributed by Utkarsh.

Output
Minimum element is: 2
Miximum  element is: 9

Time Complexity: O(N)

Auxiliary Space: O(1)

Maximum and minimum of an array using Sorting:

One approach to find the maximum and minimum element in an array is to first sort the array in ascending order. Once the array is sorted, the first element of the array will be the minimum element and the last element of the array will be the maximum element.

Step-by-step approach:

  • Initialize an array.
  • Sort the array in ascending order.
  • The first element of the array will be the minimum element.
  • The last element of the array will be the maximum element.
  • Print the minimum and maximum element.

Below is the implementation of the above approach:

C++ 
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;

struct Pair {
    int min;
    int max;
};

Pair getMinMax(int arr[], int n)
{
    Pair minmax;

    sort(arr, arr + n);

    minmax.min = arr[0];
    minmax.max = arr[n - 1];

    return minmax;
}

int main()
{
    int arr[] = { 1000, 11, 445, 1, 330, 3000 };
    int arr_size = sizeof(arr) / sizeof(arr[0]);

    Pair minmax = getMinMax(arr, arr_size);

    cout << "Minimum element is " << minmax.min << endl;
    cout << "Maximum element is " << minmax.max << endl;

    return 0;
}

// This code is contributed by Tapesh(tapeshdua420)
Java 
import java.io.*;
import java.util.*;

class Pair {
    public int min;
    public int max;
}

class Main {
    static Pair getMinMax(int arr[], int n) {
        Pair minmax = new Pair();
        Arrays.sort(arr);
        minmax.min = arr[0];
        minmax.max = arr[n - 1];
        return minmax;
    }

    public static void main(String[] args) {
        int arr[] = { 1000, 11, 445, 1, 330, 3000 };
        int arr_size = arr.length;
        Pair minmax = getMinMax(arr, arr_size);
        System.out.println("Minimum element is " + minmax.min);
        System.out.println("Maximum element is " + minmax.max);
    }
}
Python 
def getMinMax(arr):
    arr.sort()
    minmax = {"min": arr[0], "max": arr[-1]}
    return minmax

arr = [1000, 11, 445, 1, 330, 3000]
minmax = getMinMax(arr)

print("Minimum element is", minmax["min"])
print("Maximum element is", minmax["max"])
C# 
using System;

public struct Pair
{
    public int min;
    public int max;
}

class Program {
    // Function to find the minimum and maximum elements in
    // an array
    static Pair GetMinMax(int[] arr, int n)
    {
        Pair minmax = new Pair();

        // Sort the array in ascending order
        Array.Sort(arr);

        // The first element after sorting is the minimum
        minmax.min = arr[0];

        // The last element after sorting is the maximum
        minmax.max = arr[n - 1];

        return minmax;
    }

    static void Main()
    {
        int[] arr = { 1000, 11, 445, 1, 330, 3000 };
        int arrSize = arr.Length;

        // Find the minimum and maximum elements in the
        // array
        Pair minmax = GetMinMax(arr, arrSize);

        // Print the minimum and maximum elements
        Console.WriteLine("Minimum element is "
                          + minmax.min);
        Console.WriteLine("Maximum element is "
                          + minmax.max);
    }
}
Javascript 
// Function to find the minimum and maximum elements in an array
function getMinMax(arr) {
    // Create an object to store the minimum and maximum values
    const minmax = {};

    // Sort the array in ascending order
    arr.sort((a, b) => a - b);

    // Store the minimum element as the first element of the sorted array
    minmax.min = arr[0];
    // Store the maximum element as the last element of the sorted array
    minmax.max = arr[arr.length - 1];

    // Return the object containing the minimum and maximum values
    return minmax;
}

// Main function
function main() {
    // Given array
    const arr = [1000, 11, 445, 1, 330, 3000];
    
    // Call the getMinMax function to find the minimum and maximum values
    const minmax = getMinMax(arr);

    // Print the minimum element
    console.log("Minimum element is " + minmax.min);
    // Print the maximum element
    console.log("Maximum element is " + minmax.max);
}

// Call the main function to start the program
main();

Output
Minimum element is 1
Maximum element is 3000

Time complexity: O(n log n), where n is the number of elements in the array, as we are using a sorting algorithm.
Auxilary Space: is O(1), as we are not using any extra space.

Number of Comparisons:

The number of comparisons made to find the minimum and maximum elements is equal to the number of comparisons made during the sorting process. For any comparison-based sorting algorithm, the minimum number of comparisons required to sort an array of n elements is O(n log n). Hence, the number of comparisons made in this approach is also O(n log n).

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++ 
// C++ program of above implementation 
#include<bits/stdc++.h>
using namespace std;

// Pair struct is used to return 
// two values from getMinMax()
struct Pair 
{
    int min;
    int max;
}; 

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 code
int main()
{
    int arr[] = { 1000, 11, 445, 
                  1, 330, 3000 };
    int arr_size = 6;
    
    struct Pair minmax = getMinMax(arr, arr_size);
    
    cout << "Minimum element is " 
         << minmax.min << endl;
    cout << "Maximum element is " 
         << minmax.max;
         
    return 0;
} 

// This code is contributed by nik_3112
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();
}
Java 
import java.io.*;
import java.util.*;

// Java program of above implementation
public class GFG {
/* Class Pair is used to return two values from getMinMax() */
    static class Pair {

        int min;
        int max;
    }

    static Pair getMinMax(int arr[], int n) {
        Pair minmax = new  Pair();
        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 */
    public static void main(String args[]) {
        int arr[] = {1000, 11, 445, 1, 330, 3000};
        int arr_size = 6;
        Pair minmax = getMinMax(arr, arr_size);
        System.out.printf("\nMinimum element is %d", minmax.min);
        System.out.printf("\nMaximum element is %d", minmax.max);

    }

}
Python 
# Python program of above implementation

# structure is used to return two values from minMax()

class pair:
    def __init__(self):
        self.min = 0
        self.max = 0

def getMinMax(arr: list, n: int) -> pair:
    minmax = pair()

    # 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 in range(2, n):
        if arr[i] > minmax.max:
            minmax.max = arr[i]
        elif arr[i] < minmax.min:
            minmax.min = arr[i]

    return minmax

# Driver Code
if __name__ == "__main__":
    arr = [1000, 11, 445, 1, 330, 3000]
    arr_size = 6
    minmax = getMinMax(arr, arr_size)
    print("Minimum element is", minmax.min)
    print("Maximum element is", minmax.max)

# This code is contributed by
# sanjeev2552
C# 
// C# program of above implementation
using System;

class GFG 
{
    /* Class Pair is used to return 
    two values from getMinMax() */
    class Pair 
    {
        public int min;
        public int max;
    }

    static Pair getMinMax(int []arr, int n)
    {
        Pair minmax = new Pair();
        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 Code
    public static void Main(String []args) 
    {
        int []arr = {1000, 11, 445, 1, 330, 3000};
        int arr_size = 6;
        Pair minmax = getMinMax(arr, arr_size);
        Console.Write("Minimum element is {0}",
                                   minmax.min);
        Console.Write("\nMaximum element is {0}", 
                                     minmax.max);
    }
}

// This code is contributed by PrinciRaj1992
Javascript 
// JavaScript program of above implementation

/* Class Pair is used to return two values from getMinMax() */
    function getMinMax(arr, n)
    {
        minmax = new  Array();
        var i;
        var min;
        var max;

        /*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 */
    
        var arr = [1000, 11, 445, 1, 330, 3000];
        var arr_size = 6;
        minmax = getMinMax(arr, arr_size);
        console.log("\nMinimum element is " ,minmax.min +"<br>");
        console.log("\nMaximum element is " , minmax.max);

// This code is contributed by shivanisinghss2110

Output
Minimum element is 1
Maximum element is 3000

Time Complexity: O(n)
Auxiliary Space: O(1) as no extra space was needed.

Number of Comparisons:

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.

Maximum and minimum of an array using the Tournament Method:

The idea is to divide the array into two parts and compare the maximums and minimums of the two parts to get the maximum and the minimum of the whole array.

Below is the implementation of the above approach:

C++ 
// C++ program of above implementation
#include <bits/stdc++.h>
using namespace std;

// structure is used to return
// two values from minMax()
struct Pair {
    int min;
    int max;
};

struct Pair getMinMax(int arr[], int low, int high)
{
    struct Pair minmax, mml, mmr;
    int mid;

    // If there is only one element
    if (low == high) {
        minmax.max = arr[low];
        minmax.min = arr[low];
        return minmax;
    }

    // If there are two elements
    if (high == low + 1) {
        if (arr[low] > arr[high]) {
            minmax.max = arr[low];
            minmax.min = arr[high];
        }
        else {
            minmax.max = arr[high];
            minmax.min = arr[low];
        }
        return minmax;
    }

    // If there are more than 2 elements
    mid = (low + high) / 2;
    mml = getMinMax(arr, low, mid);
    mmr = getMinMax(arr, mid + 1, high);

    // Compare minimums of two parts
    if (mml.min < mmr.min)
        minmax.min = mml.min;
    else
        minmax.min = mmr.min;

    // Compare maximums of two parts
    if (mml.max > mmr.max)
        minmax.max = mml.max;
    else
        minmax.max = mmr.max;

    return minmax;
}

// Driver code
int main()
{
    int arr[] = { 1000, 11, 445, 1, 330, 3000 };
    int arr_size = 6;

    struct Pair minmax = getMinMax(arr, 0, arr_size - 1);

    cout << "Minimum element is " << minmax.min << endl;
    cout << "Maximum element is " << minmax.max;

    return 0;
}

// This code is contributed by nik_3112
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 low, int high)
{
    struct pair minmax, mml, mmr;
    int mid;

    // If there is only one element
    if (low == high) {
        minmax.max = arr[low];
        minmax.min = arr[low];
        return minmax;
    }

    /* If there are two elements */
    if (high == low + 1) {
        if (arr[low] > arr[high]) {
            minmax.max = arr[low];
            minmax.min = arr[high];
        }
        else {
            minmax.max = arr[high];
            minmax.min = arr[low];
        }
        return minmax;
    }

    /* If there are more than 2 elements */
    mid = (low + high) / 2;
    mml = getMinMax(arr, low, mid);
    mmr = getMinMax(arr, mid + 1, high);

    /* compare minimums of two parts*/
    if (mml.min < mmr.min)
        minmax.min = mml.min;
    else
        minmax.min = mmr.min;

    /* compare maximums of two parts*/
    if (mml.max > mmr.max)
        minmax.max = mml.max;
    else
        minmax.max = mmr.max;

    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, 0, arr_size - 1);
    printf("nMinimum element is %d", minmax.min);
    printf("nMaximum element is %d", minmax.max);
    getchar();
}
Java 
import java.io.*;
import java.util.*;
// Java program of above implementation
public class GFG {
    /* Class Pair is used to return two values from
     * getMinMax() */
    static class Pair {

        int min;
        int max;
    }

    static Pair getMinMax(int arr[], int low, int high)
    {
        Pair minmax = new Pair();
        Pair mml = new Pair();
        Pair mmr = new Pair();
        int mid;

        // If there is only one element
        if (low == high) {
            minmax.max = arr[low];
            minmax.min = arr[low];
            return minmax;
        }

        /* If there are two elements */
        if (high == low + 1) {
            if (arr[low] > arr[high]) {
                minmax.max = arr[low];
                minmax.min = arr[high];
            }
            else {
                minmax.max = arr[high];
                minmax.min = arr[low];
            }
            return minmax;
        }

        /* If there are more than 2 elements */
        mid = (low + high) / 2;
        mml = getMinMax(arr, low, mid);
        mmr = getMinMax(arr, mid + 1, high);

        /* compare minimums of two parts*/
        if (mml.min < mmr.min) {
            minmax.min = mml.min;
        }
        else {
            minmax.min = mmr.min;
        }

        /* compare maximums of two parts*/
        if (mml.max > mmr.max) {
            minmax.max = mml.max;
        }
        else {
            minmax.max = mmr.max;
        }

        return minmax;
    }

    /* Driver program to test above function */
    public static void main(String args[])
    {
        int arr[] = { 1000, 11, 445, 1, 330, 3000 };
        int arr_size = 6;
        Pair minmax = getMinMax(arr, 0, arr_size - 1);
        System.out.printf("\nMinimum element is %d",
                          minmax.min);
        System.out.printf("\nMaximum element is %d",
                          minmax.max);
    }
}
Python3 
# Python program of above implementation
def getMinMax(low, high, arr):
    arr_max = arr[low]
    arr_min = arr[low]

    # If there is only one element
    if low == high:
        arr_max = arr[low]
        arr_min = arr[low]
        return (arr_max, arr_min)

    # If there is only two element
    elif high == low + 1:
        if arr[low] > arr[high]:
            arr_max = arr[low]
            arr_min = arr[high]
        else:
            arr_max = arr[high]
            arr_min = arr[low]
        return (arr_max, arr_min)
    else:

        # If there are more than 2 elements
        mid = int((low + high) / 2)
        arr_max1, arr_min1 = getMinMax(low, mid, arr)
        arr_max2, arr_min2 = getMinMax(mid + 1, high, arr)

    return (max(arr_max1, arr_max2), min(arr_min1, arr_min2))


# Driver code
arr = [1000, 11, 445, 1, 330, 3000]
high = len(arr) - 1
low = 0
arr_max, arr_min = getMinMax(low, high, arr)
print('Minimum element is ', arr_min)
print('nMaximum element is ', arr_max)

# This code is contributed by DeepakChhitarka
C# 
// C# implementation of the approach
using System;

public class GFG {
    /* Class Pair is used to return two values from
     * getMinMax() */
    public class Pair {

        public int min;
        public int max;
    }

    static Pair getMinMax(int[] arr, int low, int high)
    {
        Pair minmax = new Pair();
        Pair mml = new Pair();
        Pair mmr = new Pair();
        int mid;

        // If there is only one element
        if (low == high) {
            minmax.max = arr[low];
            minmax.min = arr[low];
            return minmax;
        }

        /* If there are two elements */
        if (high == low + 1) {
            if (arr[low] > arr[high]) {
                minmax.max = arr[low];
                minmax.min = arr[high];
            }
            else {
                minmax.max = arr[high];
                minmax.min = arr[low];
            }
            return minmax;
        }

        /* If there are more than 2 elements */
        mid = (low + high) / 2;
        mml = getMinMax(arr, low, mid);
        mmr = getMinMax(arr, mid + 1, high);

        /* compare minimums of two parts*/
        if (mml.min < mmr.min) {
            minmax.min = mml.min;
        }
        else {
            minmax.min = mmr.min;
        }

        /* compare maximums of two parts*/
        if (mml.max > mmr.max) {
            minmax.max = mml.max;
        }
        else {
            minmax.max = mmr.max;
        }

        return minmax;
    }

    /* Driver program to test above function */
    public static void Main(String[] args)
    {
        int[] arr = { 1000, 11, 445, 1, 330, 3000 };
        int arr_size = 6;
        Pair minmax = getMinMax(arr, 0, arr_size - 1);
        Console.Write("\nMinimum element is {0}",
                      minmax.min);
        Console.Write("\nMaximum element is {0}",
                      minmax.max);
    }
}

// This code contributed by Rajput-Ji
Javascript 
// Javascript program of above implementation
 
    /* Class Pair is used to return two values from getMinMax() */
     class Pair {
         constructor(){
        this.min = -1;
        this.max = 10000000;
         }
    }

     function getMinMax(arr , low , high) {
        var minmax = new Pair();
        var mml = new Pair();
        var mmr = new Pair();
        var mid;

        // If there is only one element
        if (low == high) {
            minmax.max = arr[low];
            minmax.min = arr[low];
            return minmax;
        }

        /* If there are two elements */
        if (high == low + 1) {
            if (arr[low] > arr[high]) {
                minmax.max = arr[low];
                minmax.min = arr[high];
            } else {
                minmax.max = arr[high];
                minmax.min = arr[low];
            }
            return minmax;
        }

        /* If there are more than 2 elements */
        mid = parseInt((low + high) / 2);
        mml = getMinMax(arr, low, mid);
        mmr = getMinMax(arr, mid + 1, high);

        /* compare minimums of two parts */
        if (mml.min < mmr.min) {
            minmax.min = mml.min;
        } else {
            minmax.min = mmr.min;
        }

        /* compare maximums of two parts */
        if (mml.max > mmr.max) {
            minmax.max = mml.max;
        } else {
            minmax.max = mmr.max;
        }

        return minmax;
    }

    /* Driver program to test above function */
        var arr = [ 1000, 11, 445, 1, 330, 3000 ];
        var arr_size = 6;
        var minmax = getMinMax(arr, 0, arr_size - 1);
        console.log("\nMinimum element is ", minmax.min);
        console.log("<br/>Maximum element is ", minmax.max);

// This code is contributed by Rajput-Ji

Output
Minimum element is 1
Maximum element is 3000

Time Complexity: O(n)
Auxiliary Space: O(log n) as the stack space will be filled for the maximum height of the tree formed during recursive calls same as a binary tree.

Number of Comparisons:

Let the number of comparisons be T(n). T(n) can be written as follows: 

T(n) = T(floor(n/2)) + T(ceil(n/2)) + 2
T(2) = 1
T(1) = 0

If n is a power of 2, then we can write T(n) as: 

T(n) = 2T(n/2) + 2

After solving the above recursion, we get 

T(n) = 3n/2 -2

Thus, the approach does 3n/2 -2 comparisons if n is a power of 2. And it does more than 3n/2 -2 comparisons if n is not a power of 2.

Maximum and minimum of an array by comparing in pairs:

The idea is that when 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++ 
// C++ program of above implementation 
#include<bits/stdc++.h> 
using namespace std; 

// 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]; 
        } 
        
        // Set the starting index for loop 
        i = 2; 
    } 
    
    // 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]; 
        
        // Set the starting index for loop 
        i = 1; 
    } 
    
    // 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];     
        } 
        
        // Increment the index by 2 as 
        // two elements are processed in loop 
        i += 2; 
    }         
    return minmax; 
} 

// Driver code 
int main() 
{ 
    int arr[] = { 1000, 11, 445, 
                1, 330, 3000 }; 
    int arr_size = 6; 
    
    Pair minmax = getMinMax(arr, arr_size); 
    
    cout << "Minimum element is "
        << minmax.min << endl; 
    cout << "Maximum element is "
        << minmax.max; 
        
    return 0; 
} 

// This code is contributed by nik_3112
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("Minimum element is %d", minmax.min);
  printf("\nMaximum element is %d", minmax.max);
  getchar();
}
Java 
import java.io.*;
import java.util.*;
// Java program of above implementation
public class GFG {

/* Class Pair is used to return two values from getMinMax() */
    static class Pair {

        int min;
        int max;
    }

    static Pair getMinMax(int arr[], int n) {
        Pair minmax = new Pair();
        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 */
    public static void main(String args[]) {
        int arr[] = {1000, 11, 445, 1, 330, 3000};
        int arr_size = 6;
        Pair minmax = getMinMax(arr, arr_size);
        System.out.printf("Minimum element is %d", minmax.min);
        System.out.printf("\nMaximum element is %d", minmax.max);

    }
}
Python 
# Python3 program of above implementation 
def getMinMax(arr):
    
    n = len(arr)
    
    # 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]:
            mn = arr[0]
            mx = arr[1]
        else:
            mn = arr[1]
            mx = arr[0]
        
        # set the starting index for loop 
        i = 2
        
    # If array has odd number of elements then 
    # initialize the first element as minimum 
    # and maximum 
    else:
        mx = mn = arr[0]
        
        # set the starting index for loop 
        i = 1
        
    # 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]:
            mx = max(mx, arr[i + 1])
            mn = min(mn, arr[i])
        else:
            mx = max(mx, arr[i])
            mn = min(mn, arr[i + 1])
            
        # Increment the index by 2 as two 
        # elements are processed in loop 
        i += 2
    
    return (mx, mn)
    
# Driver Code
if __name__ =='__main__':
    
    arr = [1000, 11, 445, 1, 330, 3000]
    mx, mn = getMinMax(arr)
    print("Minimum element is", mn)
    print("Maximum element is", mx)
    
# This code is contributed by Kaustav
C# 
// C# program of above implementation
using System;
    
class GFG 
{

    /* Class Pair is used to return 
       two values from getMinMax() */
    public class Pair 
    {
        public int min;
        public int max;
    }

    static Pair getMinMax(int []arr, int n)
    {
        Pair minmax = new Pair();
        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 Code
    public static void Main(String []args) 
    {
        int []arr = {1000, 11, 445, 1, 330, 3000};
        int arr_size = 6;
        Pair minmax = getMinMax(arr, arr_size);
        Console.Write("Minimum element is {0}",
                                   minmax.min);
        Console.Write("\nMaximum element is {0}", 
                                     minmax.max);
    }
}

// This code is contributed by 29AjayKumar
Javascript 
// JavaScript program of above implementation 
function getMinMax(arr){
    
    let n = arr.length
    let mx,mn,i
    
    // If array has even number of elements then 
    // initialize the first two elements as minimum 
    // and maximum 
    if(n % 2 == 0){
        mx = Math.max(arr[0], arr[1])
        mn = Math.min(arr[0], 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 maximum 
    else{
        mx = mn = arr[0]
        
        // set the starting index for loop 
        i = 1
    }
        
    // 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]){
            mx = Math.max(mx, arr[i + 1])
            mn = Math.min(mn, arr[i])
        }
        else{
            mx = Math.max(mx, arr[i])
            mn = Math.min(mn, arr[i + 1])
        }
            
        // Increment the index by 2 as two 
        // elements are processed in loop 
        i += 2
    }
    
    return [mx, mn]
}
    
// Driver Code
    
let arr = [1000, 11, 445, 1, 330, 3000]
let mx = getMinMax(arr)[0]
let mn = getMinMax(arr)[1]
console.log("Minimum element is", mn,"</br>")
console.log("Maximum element is", mx,"</br>")
    
// This code is contributed by shinjanpatra

Output
Minimum element is 1
Maximum element is 3000

Time Complexity: O(n)
Auxiliary Space: O(1) as no extra space was needed.

Number of Comparisons:

The 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 + 3*(n-2)/2 = 3n/2-2, 1 comparison for initializing min and max,
and 3(n-2)/2 comparisons for rest of the elements

The third and fourth approaches make an equal number of comparisons when n is a power of 2. 
In general, method 4 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.



https://media.geeksforgeeks.org/auth/avatar.png
GeeksforGeeks
Improve
Previous Article
Square root of an integer
Next Article
Find frequency of each element in a limited range array in less than O(n) time

Similar Reads

Search an element in an unsorted array using minimum number of comparisons
Given an array of n distinct integers and an element x. Search the element x in the array using minimum number of comparisons. Any sort of comparison will contribute 1 to the count of comparisons. For example, the condition used to terminate a loop, will also contribute 1 to the count of comparisons each time it gets executed. Expressions like whil
7 min read
Second minimum element using minimum comparisons
Given an array of integers, find the minimum (or maximum) element and the element just greater (or smaller) than that in less than 2n comparisons. The given array is not necessarily sorted. Extra space is allowed. Examples: Input: {3, 6, 100, 9, 10, 12, 7, -1, 10}Output: Minimum: -1, Second minimum: 3We have already discussed an approach in below p
14 min read
Middle of three using minimum comparisons
Given three distinct numbers a, b and c find the number with a value in middle. Examples: Input : a = 20, b = 30, c = 40 Output : 30 Input : a = 12, n = 32, c = 11 Output : 12 Simple Approach: C/C++ Code // CPP program to find middle of three distinct // numbers #include &lt;bits/stdc++.h&gt; using namespace std; int middleOfThree(int a, int b, int
13 min read
Check if an element is present in an array using at most floor(N / 2) + 2 comparisons
Given an array A[] of size N and an integer X, the task is to check if X exists in A[] with no more than floor(N/2) + 2 comparisons. Note: For any index i, (i &lt; N) or (A[i] == X) are considered as separate comparisons. Examples: Input: A[] = {-3, 5, 11, 3, 100, 2, 88, 22, 7, 900, 23, 4, 1}, X = 88Output: Yes 8Explanation: X = 88 exists in the gi
7 min read
Minimum comparisons required to find the only heavier ball from N balls
Given N (N &gt; 1) number of balls and a weight balancing machine. There are N-1 balls of the same weight and one ball heavier than the others. The task is to find out the minimum number of times weighing is required to find the heavier ball where any number of balls can be weighted each time. Note: The weight balancing machine can tell relative we
5 min read
Number of comparisons in each direction for m queries in linear search
Given an array containing N distinct elements. There are M queries, each containing an integer X and asking for the index of X in the array. For each query, the task is to perform linear search X from left to right and count the number of comparisons it took to find X and do the same thing right to left. In the end, print the total number of compar
7 min read
Comparisons involved in Modified Quicksort Using Merge Sort Tree
In QuickSort, ideal situation is when median is always chosen as pivot as this results in minimum time. In this article, Merge Sort Tree is used to find median for different ranges in QuickSort and number of comparisons are analyzed.Examples: Input : arr = {4, 3, 5, 1, 2} Output : 11 Explanation We have to make 11 comparisons when we apply quick so
15+ min read
How to make Mergesort to perform O(n) comparisons in best case?
As we know, Mergesort is a divide and conquer algorithm that splits the array to halves recursively until it reaches an array of the size of 1, and after that it merges sorted subarrays until the original array is fully sorted. Typical implementation of merge sort works in O(n Log n) time in all three cases (best, average and worst). We need to red
3 min read
Multiple comparisons in a C++ priority queue?
What is a Priority Queue? A Priority Queue is an abstract data type that is similar to a queue, and every element has some priority value associated with it. The priority of the elements in a priority queue determines the order in which elements are served (i.e., the order in which they are removed). If in any case, the elements have the same prior
5 min read
Minimum number greater than the maximum of array which cannot be formed using the numbers in the array
Given an array arr[] of integers, the task is to find the minimum number greater than the maximum element from the array which cannot be formed using the numbers in the array (adding elements to form some other number). If no such element exists then print -1. Examples: Input: arr[] = {2, 6, 9} Output: -1 There is no such number greater than 9 that
9 min read
Article Tags :
Practice Tags :
We use cookies to ensure you have the best browsing experience on our website. By using our site, you acknowledge that you have read and understood our Cookie Policy & Privacy Policy
Lightbox