How to find max. and min. in array using minimum comparisons?

1. Pick 2 elements(a, b), compare them. (say a > b)
2. Update min by comparing (min, b)
3. Update max by comparing (max, a)

This way you would do 3 comparisons for 2 elements, amounting to 3N/2 total comparisons for N elements.

A somewhat different approach, which uses integer arithmetic instead of comparisons (which wasn't explicitly prohibited)

for(int i=0;i<N;i++) {
  xmin += x[i]-xmin & x[i]-xmin>>31;
  xmax += x[i]-xmax & xmax-x[i]>>31;
}

Trying to improve on the answer by srbh.kmr. Say we have the sequence:

A = [a1, a2, a3, a4, a5]

Compare a1 & a2 and calculate min12, max12:

if (a1 > a2)
  min12 = a2
  max12 = a1
else
  min12 = a1
  max12 = a2

Similarly calculate min34, max34. Since a5 is alone, keep it as it is...

Now compare min12 & min34 and calculate min14, similarly calculate max14. Finally compare min14 & a5 to calculate min15. Similarly calculate max15.

Altogether it's only 6 comparisons!

This solution can be extended to an array of arbitrary length. Probably can be implemented by a similar approach to merge-sort (break the array in half and calculate min max for each half).

UPDATE: Here's the recursive code in C:

#include <stdio.h>

void minmax (int* a, int i, int j, int* min, int* max) {
  int lmin, lmax, rmin, rmax, mid;
  if (i == j) {
    *min = a[i];
    *max = a[j];
  } else if (j == i + 1) {
    if (a[i] > a[j]) {
      *min = a[j];
      *max = a[i];
    } else {
      *min = a[i];
      *max = a[j];
    }
  } else {
    mid = (i + j) / 2;
    minmax(a, i, mid, &lmin, &lmax);
    minmax(a, mid + 1, j, &rmin, &rmax);
    *min = (lmin > rmin) ? rmin : lmin;
    *max = (lmax > rmax) ? lmax : rmax;
  }
}

void main () {
  int a [] = {3, 4, 2, 6, 8, 1, 9, 12, 15, 11};
  int min, max;
  minmax (a, 0, 9, &min, &max);
  printf ("Min : %d, Max: %d\n", min, max);
}

Now I cannot make out the exact number of comparisons in terms of N (the number of elements in the array). But it's hard to see how one can go below this many comparisons.

UPDATE: We can work out the number of comparisons like below:

At the bottom of this tree of computations, we form pairs of integers from the original array. So we have N / 2 leaf nodes. For each of these leaf nodes we do exactly 1 comparison.

By referring to the properties of a perfect-binary-tree, we have:

leaf nodes (L) = N / 2 // known
total nodes (n) = 2L - 1 = N - 1
internal nodes = n - L = N / 2 - 1

For each internal node we do 2 comparisons. Therefore, we have N - 2 comparisons. Along with the N / 2 comparisons at the leaf nodes, we have (3N / 2) - 2 total comparisons.

So, may be this is the solution srbh.kmr implied in his answer.

go for divide and conquer !

1,3,2,5

for this finding min,max will take 6 comparisons

but divide them

1,3 ---> will give min 1 and max 3 in one comparison
2,5 ---> will give min 2 and max 5 in one comparison 

now we can compare two mins and maxs

min(1,2) --> will give the final min as 1 (one comparison)
max(3,5) ---> will give the final max as 5 (one comparison)

so totally four comparisons to find both min and max.