문제 해결 패턴 / 분할과 정복 (이진탐색 배우며 추가 예정)

 

분할과 정복은 주로 배열이나 문자열 같은 큰 규모의 데이터셋을 처리한다. 

퀵 정렬, 병합 정렬, 이진 탐색 등이 분할 정복 알고리즘이다.

 

 

 

 

정렬된 arr에서 val의 인덱스 넘버를 찾아라(없으면 -1 리턴)

function binarySearch(arr, val) {
  let min = 0;
  let max = arr.length - 1;

  while (min <= max) {
    let mid = Math.floor((min + max) / 2);
    let currentEl = arr[mid];

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