분할 정복 (Divide and Conquer)

-데이터 셋을 작은 부분으로 나누고 해결을 반복한다. 이러한 방법을 사용하면 시간복잡도가 크게 감소한다.

-정렬, 탐색 등 많은 다른 알고리즘에서 사용된다. 

- 주로 배열이나 문자열 같은 큰 규모의 데이터셋을 처리한다.

 

 

예시: 배열에서 특정 값을 찾는 경우. 선형탐색으로 찾을 수도 있지만 아래처럼 이진탐색 할 수도 있다.

function search(array, val) {
    // 단 배열이 정렬돼 있어야 함
    let min = 0;
    let max = array.length -1;

    while (min <= max) {
        let middle = Math.floor((min+max)/2);
        let currentElement = array[middle];

        if(array[middle] < val) {
            min = middle + 1;
        }
        else if (array[middle] > val) {
            max = middle - 1;
        }
        else {
            return middle;
        }
    }
    return -1;
}