divide and conquer

divide and conquer 알고리즘은 규모가 큰 배열이나 문자열에 유용한 패턴으로, 큰 데이터셋을 다루기 쉬운 작은 데이터셋으로 나누어 최종적인 답을 구하는 패턴이다. 큰 데이터셋에서 시간 복잡도를 낮추는 데에 유용하다.

예를 들어, 정렬된 배열에서 특정 숫자의 인덱스를 찾는 데에 사용할 수 있다. 분할 정렬 알고리즘에는 여러 종류가 있지만, 먼저 이진 탐색을 알아보자.

[1,2,3,4,5,6,7,,8,9, 11, 14, 16, 17, 18, 20, 24, 25, 43, 54, 65, 77, 83, 87 ... 99999]

위와 같은 값에서 특정 숫자를 찾기 위해서는 일반적으로 for문을 사용할 수 있다. 그러나 해당 방법을 이용할 경우, 어느 쪽에서 먼저 인덱스를 찾기 시작함과 관계없이 시간복잡도가 높아지게 된다.

그러나 이진 탐색을 이용할 경우, 시간복잡도가 O(N)으로 줄어들 수 있다.

const search = (arr, value) => {
  let min = 0;
  let max = arr.length - 1;
  
  while(min <= max) {
    let middleIndex = Math.floor((min + min) / 2); // 중간 값
    let currentElement = arr[middleIndex];
    
    if(arr[middleIndex] < value) { // 중간 값이 기준 숫자보다 작으면
    	min = middle + 1;
    } else if (arr[middleIndex] > value) {
    	max = middle - 1;
    } else {
    	return middleIndex
    }
  }
  return -1;
}