배열 최댓값, 최솟값 찾기 (분할 정복, Divide and Conquer)

배열에서 분할 정복을 이용하여 최댓값을 찾는 예시이다.

배열을 왼쪽, 오른쪽 반씩 나누고 왼쪽 반에서 최댓값을 재귀적으로 찾는다.

오른쪽도 마찬가지 방법으로 반복한다.

이렇게 왼쪽, 오른쪽에서 찾은 최댓값을 비교하여 더 큰 값을 최댓값으로 설정한다.

최솟값 찾기는 부호의 방향만 바꾸어주면 된다.

#include <stdio.h>

int find_max_index(int arr[], int left, int right) {
    if (left == right)  // 배열 길이 1
        return left;

    int mid = (left + right) / 2;
    int left_max_index, right_max_index;

    left_max_index = find_max_index(arr, left, mid);
    right_max_index = find_max_index(arr, mid + 1, right);

    // 더 큰 값의 인덱스를 return
    return arr[left_max_index] > arr[right_max_index] ? left_max_index : right_max_index;
}

int main() {
    int arr[] = {50, 20, 10, 5, 1, 25, 40, 100, 3, 15, 60, 70};
    int max_index = find_max_index(arr, 0, (sizeof(arr) / sizeof(int)) - 1);

    printf("Max Index: %d, Max Value: %d\n", max_index, arr[max_index]);
}