분할 정복을 이용한 최솟값, 최댓값 찾기

분할 정복을 이용한 최솟값, 최댓값 찾는 알고리즘.
배열을 계속 해서 반으로 나누면서 각 배열의 최솟값, 최댓값을 다른 배열과 비교한다.
반으로 나누고 최소, 최댓값들을 반복해서 비교하기 때문에 재귀를 사용한다.

---

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;
    }
}

---

트리에서 내부 노드들의 합은 리프 노드들보다 하나 작은 n-1개 이다.

(n/2-1)개를 2번씩 비교하므로 2*(n/2-1) + n/2 = 3n/2-2 =>
따라서 시간복잡도는 O(N)이다.