最小值最大值

同时找出一个序列中的最小值最大值，一般方法需要2*（n-1）的比较次数。

运用分治，可以降低比较次数。

基本思路：把序列分为两部分，找出前半部分的最小值与最大值，再找出后半部分的最小值与最大值，然后比较得出整个序列的最小值与最大值。一直划分到序列只有两个元素时，则直接比较两个元素并返回结果。

比较次数分析：f(1) = 1; f(2) = 1; 当n为奇数时，f(n) = f([n/2]) + f(n-[n/2]) + 2; 当n为偶数时，f(n) = 2*f(n/2) + 2.可以证明比较次数最多不超过3*[n/2]。

import java.util.Random;
import java.util.Arrays;

public class MinMax{
    
    private class MM{
        //return type
        public int min;
        public int max;
        public MM(int min, int max){
            this.min = min;
            this.max = max;
        }
        public String toString(){
            //print
            return "Min: " + min + "\n" + "Max: " + max;
        }
    }

    public MM minMax(int[] A){
        return minMaxDo(A, 0, A.length-1);
    }

    private MM minMaxDo(int[] A, int low, int high){
        if(high - low <= 1){
            if(A[low] < A[high])
                return new MM(A[low], A[high]);
            return new MM(A[high], A[low]);
        }
        //Divide and Conquer
        int mid = (low + high) / 2;
        MM x = minMaxDo(A, low, mid);
        MM y = minMaxDo(A, mid+1, high);
        int min, max;
        if(x.min < y.min)
            min = x.min;
        else
            min = y.min;
        if(x.max > y.max)
            max = x.max;
        else
            max = y.max;
        return new MM(min, max);
    }

    public static void main(String[] args){
        //Unit Testing
        MinMax test = new MinMax();
        int n = 10;
        int[] A = new int[n];
        Random rand = new Random();
        for(int i = 0; i < A.length; i ++){
            A[i] = rand.nextInt() % 100;
        }
        MM x = test.minMax(A);
        System.out.println(Arrays.toString(A));
        System.out.println(x);
    }
}