Find maximum and minimum

Problem

Given an array of integers, find the maximum and minimum of the array.

Constraint

Find the answer in minimum number of comparisons.

Brute force

We can keep two variables named max and min. We can iterate over the list and compare each number with the min and the max, if the number is greater than the max update max, if the number is less than the min, update the min. In this brute force solution the number of comparison is 2*n.

Better solution

If rather than comparing each number with max and min, we can first compare the numbers in pair with each other. Then compare the larger number with max and compare the smaller number with min. in this way the number of comparison for a pair of numbers are 3. So number of comparisons are 1.5 *n.

Code

public class FindMinMax
{

 public static void main(String[] args)
 {
  int[] arr = {4, 3, 5, 1, 2, 6, 9, 2, 10, 11};
  int max = arr[0];
  int min = arr[0];
  int i = 0;
  for (; i < arr.length / 2; i++)
  {
   int num1 = arr[i * 2];
   int num2 = arr[i * 2 + 1];
   if (arr[i * 2] >= arr[i * 2 + 1])
   {
    if (num1 > max)
     max = num1;
    if (num2 < min)
     min = num2;
   }
   else
   {
    if (num2 > max)
     max = num2;
    if (num1 < min)
     min = num1;
   }
  }
  if (i * 2 < arr.length)
  {
   int num = arr[i * 2];
   if (num > max)
    max = num;
   if (num < min)
    min = num;
  }
  System.out.println("maximum= " + max);
  System.out.println("minimum= " + min);
 }

}
        

Further discussion

Now let's think what will happen if instead of two numbers we take three numbers and then first find the largest and smallest of them and then compare these two numbers with max and min. To find the largest and smallest among 3 numbers, we need 3 comparisons in worst case and 2 comparisons in best case. The average case is 2.5. So for 3 numbers we need total 5 comparisons in worst case and 4.5 in average case. So in worst case comparisons per number is 1.6 and average case 1.5. Similarly we can derive that the worst case comparison is never less than 1.5. and best and average case is equal in case of taking numbers in pair.

Divide and conquer method

In this approach we are dividing the list in two parts, each part is recursively providing the min and max of that part and then two min max are compared to decide the ultimate min and max. Recursively when the array is reduced to only a single element then the element itself become min and max.

Code

public class FindMinMax2
{
 public static void main(String[] args)
 {
  int[] arr = {4, 3, 5, 1, 2, 6, 9, 2, 10, 11, 12};
  MinMax result = findMinMaxRecursive(arr, 0, arr.length - 1);
  System.out.println("maximum= " + result.max);
  System.out.println("minimum= " + result.min);
 }

 private static MinMax findMinMaxRecursive(int[] arr, int i, int j)
 {
  if (i > j)
   return null;
  if (i == j)
   return new MinMax(arr[i], arr[i]);
  else
  {
   MinMax left;
   MinMax right;
   left = findMinMaxRecursive(arr, i, (i + j) / 2);
   right = findMinMaxRecursive(arr, (i + j) / 2 + 1, j);
   if (left == null)
    return right;
   else if (right == null)
    return left;
   else
   {
    return new MinMax(Math.min(left.min, right.min), Math.max(
      left.max, right.max));
   }
  }
 }
}

class MinMax
{
 public int min;
 public int max;

 public MinMax(int min, int max)
 {
  this.min = min;
  this.max = max;
 }
}