[JS 알고리즘 - 탐색] 분할과 정복 패턴 ( Divide and Conquer )

아래 강의를 듣고 내용을 정리한 포스트 입니다.

https://www.udemy.com/course/best-javascript-data-structures/

JavaScript (JS) Algorithms and Data Structures Masterclass

 

이 알고리즘은 주로 배열이나 문자열 같은 큰 규모의 데이터셋을 처리합니다.
각종 정렬 알고리즘에도 이 개념이 포함되고, 이진 탐색에도 포함됩니다.
이진 탐색 트리 에서도 이 개념이 포함됩니다.

이진 검색은 선형 검색보다 훨씬 빠른 속도로 값을 찾을 수 있습니다. 이 알고리즘은 배열이 정렬되어 있어야 하며, 배열의 중간 값과 찾고 있는 값을 비교하여 검색 범위를 반으로 줄여나가는 방식으로 작동합니다. 이는 O(log n)의 시간 복잡도를 가지며, 배열의 크기가 클수록 더욱 빠른 성능을 보여줍니다.

예제 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

위 함수는 정렬된 숫자를 지닌 배열을 취합니다. 배열은 정렬된 상태여야 하고, 두번째 인자로 전달받은 index의 값을 반환합니다.

const search = (array: number[], val: number) => {
  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;
};

위의 코드에서는 이진 검색을 구현하는 방법을 보여주고 있습니다. 함수는 배열과 찾고자 하는 값을 인수로 받아 검색을 수행하며, 배열이 정렬되어 있다는 가정 하에 작동합니다. 이진 검색의 주요 원리는 while 루프 안에 있습니다. 이 알고리즘에서는 배열의 중간값을 선택하고, 이 값과 찾고자 하는 값을 비교합니다. 만약 중간값이 찾고자 하는 값보다 작으면 검색 범위를 중간값의 오른쪽으로 이동시키고, 중간값이 찾고자 하는 값보다 크면 검색 범위를 중간값의 왼쪽으로 이동시킵니다. 이를 반복하여 값을 찾을 때까지 검색 범위를 반으로 줄여나가게 됩니다.