✔️ 4.Divide and Conquer(분할과 정복)

1. 데이터셋을 작은 부분으로 나누고 데이터의 하위집합으로 프로세스를 반복
2. 시간복잡도를 크게 줄일 수 있다
3. 퀵 정렬, 병합 정렬, 이진 탐색

💻 예제 1

정렬된 숫자 배열과 검색하려는 숫자를 인자로 받아 해당 위치의 인덱스를 반환하는 함수 search를 작성하시오
(단, 값이 없을 경우 -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

🔎 내가 했던 풀이

🔸 풀이 전 어떻게 구성할지 생각해봤다
1. 배열을 순회하면서 비교 후 검색 할 num과 같으면 해당 인덱스 리턴 없으면 -1리턴

const search = (arr, num) => {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === num) return i;
  }
  return -1;
};

O(N)의 시간 복잡도를 가진다.
-> 배열에 있는 첫번째 원소부터 n번째 원소까지 하나하나 탐색하므로

🔎 해답

1. Binary Search 이진탐색
   : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. (정렬되어 있지 않으면 쓸 수 없음!)

   => 시간복잡도 log(N) : 정렬된 배열에서 범위를 반씩 줄여가면서 탐색하기 때문에!

🔸 풀이의 경우 주석으로 내가 이해 한 부분을 작성해봤다.

const search = (arr, num) => {
  //서치 할 범위 초기에는 전체로 잡는다
  let min = 0;
  let max = arr.length - 1;

  while (min <= max) {
    let mid = Math.floor((min + max) / 2); //중간 인덱스값을 구한다
    let currentElem = arr[mid];

    if (currentElem < num) {
      min = mid + 1; // 중간 값이 검색 할 num보다 작다? 그 중간값 이전 값은 비교 할 필요 없으므로 min 값(비교군 첫번째 인덱스)에 비교 했던 mid값 다음인 [mid+1 ]을 할당한다
    } else if (currentElem > num) {
      max = mid - 1; // 중간 값이 검색 할 num보다 크다? 그 중간값 이후 부터는 비교 할 필요 없으므로 max값(비교군 마지막 인덱스)에 mid값 이전인 [mid-1]을 할당한다
    } else {
      return mid; //같다면? 해당 인덱스 mid 값을 리턴한다.
    }
  }
  return -1; //없으면 -1리턴
};

🤨이진탐색..너란 녀석 나중에 따로 정리해보겠어...