分割征服を使って最高価格、最低価格を探す

分割征服を利用して最高価格、最低価格のアルゴリズムを探す.
並び続け、半分に分けて、各並びの最切り上げ、最値を他の並びと比較します.
半々に分けて、最小値と最高値の比較を繰り返すので、再帰を使います.

public class Main
{
    
    public static int[] findMinMax(int[] arr, int start, int end)
    {
        int mid;
        int[] result = new int[2]; // 결과 배열. [0]이 최솟값, [1]이 최댓값
        int[] left = new int[2];
        int[] right = new int[2];
        
        if (start==end) // 요소가 1개일때
        {
            result[0] = arr[start];
            result[1] = arr[start];
        }
        else if (start == end - 1) // 요소 2개일때
        {
            if (arr[start] < arr[end])
            {
                result[0] = arr[start];
                result[1] = arr[end];
            }
            else
            {
                result[0] = arr[end];
                result[1] = arr[start];
            }
        }
        else // 요소 3개 이상일때
        {
            mid = (start + end) / 2;
            left = findMinMax(arr, start, mid); // 재귀 이용해 왼쪽, 오른쪽 최대최소 구함
            right = findMinMax(arr, mid+1, end);
            
            if (left[0] < right[0]) result[0] = left[0];
            else result[0] = right[0];
            if (left[1] < right[1]) result[1] = right[1];
            else result[1] = left[1];
        }
        return result;
    }
    
	public static void main(String[] args) 
	{
	    int[] arr = {9,8,3,7,4,2};
	    int[] ans = new int[2];
	    ans = findMinMax(arr, 0, arr.length-1);
		System.out.println("min is :"+ans[0]);
		System.out.println("max is :"+ans[1]);
	}
}

public static int func(int[] arr, int start, int end)
{ // simple ver.
    int mid;
    if (start == end) // 요소가 1개일때
        return arr[start];
   
    else 
    {
        mid = (start + end) / 2;
        int left = func(arr, start, mid);
        int right = func(arr, mid+1, end);
        
        return left > right ? left : right;
    }
}

ツリー内の内部ノードの和はリーフノードより1つ小さいn-1個である.

(n/2-1)個比較2回、2*(n/2-1)+n/2=3 n/2-2=>
従って,時間複雑度はO(N)であった.