Finding maximum and minimum of an array in a single recursive function

Question

The following program utilizes the Divide and Conquer paradigm and uses the idea of Merge Sort to find the maximum and minimum element of an array recursively. This was an assignment that asked to do it recursively, I've coded the solution but my question is does it minimize the number of comparisons necessary to find the values of a minimum and maximum?

#include <stdio.h>
#include <limits.h>


void max(int *ptr, int lower, int upper, int *maximum, int *min)
{
  //returns the maximum element of the array
  int mid;
  int left, right;

  if(lower == upper){
    if(ptr[lower] > *maximum)
      {
         *maximum = ptr[lower];
      }
    if(ptr[lower] < *min)
      {
         *min = ptr[lower];
      }
    return;
  }

  mid = (lower+upper) /2;

  max(ptr, lower, mid, maximum, min);
  max(ptr, mid+1, upper, maximum, min);
}

int main()
{
  int n;
  int i;

  int *ptr;

  int maximum=-1;
  int minimum=INT_MAX;


  printf("\nEnter the size of the array : ");
  scanf("%d", &n);

  ptr = (int *) malloc(sizeof(int)*n);

  printf("Enter the contents of the array : ");

  for(i=0 ; i<n; i++)
    scanf("%d", &ptr[i]);

  max(ptr,0,n-1,&maximum,&minimum);

  printf("\n Maximum element is : %d", maximum);
  printf("\n Minimum element is : %d", minimum);

  free(ptr);

  return 0;
}

Answer 1

does it minimize the number of comparisons necessary to find the values of a minimum and maximum?

Short answer: no

---

Your code actually requires

n * 4 - 1

comparisons where n is the number of items in the array.

The above counting 1 comparison to check lower==upper and in case it evaluates true 2 more comparisons to check max and min

If you simply parse the array from the beginning to the end with a for loop you'll need

n * 2

comparisons.

But wait: as you also need a for loop at every iteration there is an additional comparison to check if loop ended.

So actually there are

n * 3

comparisons.

The code you posted is not efficient, furthermore you have to calculate mid at each call to max() plus the overhead of recursive function calling.

As you have an unordered array or numbers and you have to find min and max the fastest solution is (as others pointed out) to iterate the array.

If you want a proof you can test it...

Here is the output:

Elements count : 10000
Maximum element is : 99964
Minimum element is : 9
Number of comparisons : 39999

Below is your code with test embedded

(I just added a global g_comparisons that gets incremented before each comparison - also the process of array population is done programmatically with random values)

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int g_comparisons = 0;

void max(int *ptr, int lower, int upper, int *maximum, int *min)
{
    //returns the maximum element of the array
    int mid;
    g_comparisons ++;
    if(lower == upper){
        g_comparisons += 2;
        if(ptr[lower] > *maximum)
        {
            *maximum = ptr[lower];
        }
        if(ptr[lower] < *min)
        {
            *min = ptr[lower];
        }
        return;
    }

    mid = (lower+upper) /2;

    max(ptr, lower, mid, maximum, min);
    max(ptr, mid+1, upper, maximum, min);
}

int main()
{
    int n;
    int i;

    int *ptr;

    int maximum=-1;
    int minimum=INT_MAX;


    //printf("\nEnter the size of the array : ");
    //scanf("%d", &n);

    n = 10000;

    ptr = (int *) malloc(sizeof(int)*n);

    // printf("Enter the contents of the array : ");

    for(i=0 ; i<n; i++)
    {
    //    scanf("%d", &ptr[i]);
        ptr[i] = rand()%100000;
    }

    max(ptr,0,n-1,&maximum,&minimum);

    printf("\n Elements count : %d" , n);

    printf("\n Maximum element is : %d", maximum);
    printf("\n Minimum element is : %d", minimum);

    printf("\n Number of comparisons : %d\n", g_comparisons);

    free(ptr);

    return 0;
}

Answer 2

Use an else to minimize comparisons. If you found a new maximum then it could not be a minimum (or the converse if you want):

if (ptr[lower] > *maximum) {
  *maximum = ptr[lower];
} else {
  if (ptr[lower] < *min) {
    *min = ptr[lower];
}

For this to work, you need to initialize min and max to any value in the array:

minimum = maximum = ptr[0];

Note that in your case, a recursive schema is absolutely unuseful, a simple incremental parsing of the array is sufficient and will let you save a lot of operations (computation of the middle, test of the base case, passing parameters, function calls). An alternative could be to compute your results while scanning the inputs...

Answer 3

There are two things I want to point out 1. If the array is sorted then finding minimum and Maximum takes O(1) time. 2. If array is not in sorted order then doing sorting does not help you if your objective is only to find minimum and maximum number. Here is the reason: Any comparison based sorting algorithm takes Ω(nlogn) time whereas maximum and minimum can be found together in a single for loop iteration. By each time comparing next element with the maximum and minimum found so far. So use only one for loop. It will be simple

If your assignment is forcing you to do it recurssively, still it can be done in O(n) comparisons. Simply instead of writing a for loop use a recurssion function with slight modification in the code written in the loop.