/**
 * Finding the minimum and maximum of a series of elements in the minimal number of comparisions
 * 
 * @author (Stefan Edelkamp) 
 * @version (2013)
 */

import java.util.Random; 

public class MinMax
{
    int [] a;
    public class MM { int min; int max; };    
    /**
     * Constructor for objects of class MinMax, N is number of elements
     */
    public MinMax(int N) {
	  Random r = new Random();
	  a = new int[N];
      for (int i=0;i<N;i++) {
        a[i] = r.nextInt(1000);
        System.out.print(a[i]+ ",");
      }
      System.out.println();
    }
    /**
     * search for minimum and maximum concurrently by divide and conquer
     * 
     * @param  x   left index range
     * @param  y   right index range 
     */
    MM search(int x, int y)  { 
      MM m = new MM();
      if (y <= x+1) { m.min = a[x]<a[y] ? x : y; m.max = a[x]<a[y] ? y : x; }
      else { // y > x+1, recursive call required
        MM l = search(x,(x+y)/2), r = search((x+y)/2+1,y);
        m.min = a[l.min] < a[r.min] ? l.min : r.min; 
        m.max = a[l.max] > a[r.max] ? l.max : r.max; 
      }
      return m; 
    }
}