2023-04-14 금요일

✏️ 무엇을 배웠나

1. 이분 탐색 (Binary Search)

이분 탐색 aka 이진 탐색은 정렬된 데이터 내에서 특정 데이터를 찾을 때 선형 탐색보다 효율적인 탐색 방법이다.

이분 탐색의 핵심은 분할과 반복이다. 먼저 전체 데이터를 2개로 분할한 다음, 내가 찾는 데이터가 어느 범위에 속하는지 판단한다. 이것을 반복하면서 지속적으로 검색 범위를 50%씩 줄여나간다. 이때 시간복잡도는 O(logN)이다.

자바스크립트에서 배열의 특정 요소를 찾는 이분 탐색은 아래처럼 구현할 수 있다.

const sortedArray = [1, 3, 4, 5, 7, 9, 10];

const binarySearch = (array, target) => {
  // 검색 범위를 지정하는 변수를 선언함
  let min = 0; // 최소값은 첫번째 인덱스
  let max = array.length - 1; // 최대값은 마지막 인덱스

  /*
  1. 중간값을 구한 다음에 target과 비교해서 target이 속하는 범위를 반복해서 줄인다
  2. 중간값이 target과 같을 때 그 값을 return한다
  */
  while (min <= max) {
    const mid = Math.floor((min + max) / 2);

    if (array[mid] === target) {
      console.log('target', target)
      console.log('element',array[mid])
      console.log('index', mid)
      return mid;
    }

    if (array[mid] < target) {
      min = mid + 1;
    } else {
      max = mid - 1;
    }
  }

  return "그런 거 없음";
};

binarySearch(sortedArray, 1);

핵심 아이디어

• 데이터 내 최소값과 최대값을 사용해 검색 범위를 잡아준다
• 데이터 내 중간값을 사용해 검색 범위를 반으로 나눠준다
• 중간값과 내가 찾는 데이터를 비교해 범위를 좁혀나가면서 검색한다.