Divide and Conquer

정의

- 이 패턴은 큰 데이터를 작은 크기로 나눈 다음 작은 데이터들을 반복해서 푸는 형식이다.

- 이 패턴은 배열에 많은 데이터나 리스트에 많은 데이터인 경우 시간 복잡도를 많이 줄일 수 있다. 

 

예시] 아래 처럼 정렬된 정수과 오른쪽에 숫자를 보면서 오른쪽 숫자의 인덱스를 반환하시고 만약 숫자가 없으면 -1로 반환 하시오

search([1,2,3,4,5,6], 4) // 3

search([1,2,3,4,5,6], 6) // 5

search([1,2,3,4,5,6], 11) // -1

 

좋지 않는 해답

function search (arr, val) {

  for(let i = 0; i < arr.length; i++) {

    if ( arr[i] === val ) {

      return i;

    }

  }

  return -1;

}

 

좋은 해답 - 시간 복잡도(Log(N)) 이진 방식으로 찾기!

function search(arr, val){
    if(arr.length === 0){return -1;}
    arr.sort( (a,b) => a-b)
    
    let min = 0;
    let max = arr.length-1;

    let middle = Math.floor( (min+max)/2 );

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

    
    for(let i = min; i <= max; i++){
        if(arr[i] === val){
            return i;
        }
    }
    return -1;
   
}