算法基础之寻找最大最小值

分治思想求解N个数中的最大值max和最小值min:分别求出前后N/2个数中的max和min，然后取较大的max和较小的min。
比较次数：f(N) = 2*f(N/2) + 2 = ... = 1.5N - 2。

import java.util.Arrays;

/**
 * 寻找最大最小值 【分治】
 * 
 * @author aaron-han
 * 
 */
public class FindMaxMin {

	public static void main(String[] args) {
		int[] arr = com.utils.Utils.randomIntArray();
		System.out.println(Arrays.toString(arr));
		int[] result = findMaxMin(arr, 0, arr.length - 1);
		System.out.println("Max = " + result[1] + " , Min = " + result[0]);
	}

	// 0存小 1存大
	public static int[] findMaxMin(int[] arr, int low, int high) {
		if (high - low <= 1) {
			return arr[low] < arr[high] ? new int[] { arr[low], arr[high] }
					: new int[] { arr[high], arr[low] };
		}

		int[] left = findMaxMin(arr, low, low + (high - low) / 2);
		int[] right = findMaxMin(arr, low + (high - low) / 2 + 1, high);

		return new int[] { left[0] < right[0] ? left[0] : right[0],
				left[1] > right[1] ? left[1] : right[1] };
	}

}