Data Structures and Algorithm: Find maximum and minimum

Data Structures and Algorithm: Find maximum and minimum

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

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.

 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;
  }

Divide and  methodconquer

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.

http://www.fgdsb.com/2015/01/03/max-and-min/
http://somnathkayal.blogspot.in/2012/08/finding-maximum-and-minimum-using.html

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

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

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

           .

           .

           .

           = 2^k-1 T(2) + ∑(1≤i≤k-1) 2^k

           = 2^{k-1 +} 2^k – 2

           = 3n/2 – 2 = O(n)

Note that 3n/2 – 2 is the best, average, worst case number of comparison when n is a power of two.

Read full article from Data Structures and Algorithm: Find maximum and minimum