이진 탐색

패스트캠퍼스 코딩 테스트 강좌, 잔재미코딩 님의 수업을 참고했습니다.

이진 탐색(Binary Search)

• 탐색할 자료를 둘로 나누어 해당 데이터가 있을 만한 곳을 탐색하는 방법
• 무작위 정수가 담긴 배열에서 특정 정수를 찾아야 할 때, 해당 배열을 오름차순으로 정렬하고, 가운데 인덱스의 요소를 확인한다. 값이 찾고자 하는 값보다 크면 가운데 인덱스에서 끝 인덱스의 가운데 인덱스를 또 확인하고, 작으면 반대로 진행한다.

• [저작자] by penjee.com 이미지 출처

분할정복 알고리즘과 이진 탐색

• 분할 정복
  • Divide: 문제를 하나 혹은 둘 이상으로 나눈다.
  • Conquer: 나눠진 문제가 충분히 작고 해결할 수 있다면 해결하고, 그렇지 않다면 다시 나눈다.
    • 재귀 함수를 많이 사용한다.
• 이진 탐색
  • Divide: 배열을 두 개의 서브 배열로 나눈다.
  • Conquer
    • 검색할 숫자 > 중간값이면, 뒷 부분의 서브 리스트에서 검색할 숫자를 찾는다.
    • 검색할 숫자 < 중간값이면, 앞 부분의 서브 리스트에서 검색할 숫지를 찾는다.

구현

• 데이터가 오름차순이나 내림차순으로 정렬되어 있는 상태에서 진행

재귀 함수를 이용하여 구현

const binarySearch = (arr, target) => {
  // arr 오름차순 정렬
  arr.sort((a, b) => a - b);

  // 재귀 함수 종료 조건
  if (arr.length === 0) return false;
  if (arr.length === 1 && target === arr[0]) return true;
  if (arr.length === 1 && target === arr[0]) return false;

  // 중간값 인덱스
  const mid = Math.floor(arr.length / 2);

  if (target === arr[mid]) return true;

  if (target > arr[mid]) {
    return binarySearch(arr.slice(mid + 1, arr.length - 1), target);
  } else {
    return binarySearch(arr.slice(0, mid), target);
  }
};

console.log(
  binarySearch([1, 5, 3, 7, 50, 23, 456, 678, 789, 1256, 4567, 111], 789)
);

반복문을 이용한 구현

이쪽이 좀더 맘에 든다. 새로운 배열을 만들지 않기 때문에 target의 인덱스를 좀더 쉽게 구할 수 있다.

// 데이터가 담긴 배열 arr, 찾고자 하는 데이터 target
const binarySearch = (arr, target) => {
  // arr 오름차순 정렬
  arr.sort((a, b) => a - b);

  let min = 0; // 최소값의 인덱스
  let max = arr.length - 1; // 최대값의 인덱스

  // max가 min보다 작다는 것은 배열의 길이가 0 또는 target이 arr에 없다는 뜻.
  while (min <= max) {
    // 중간값의 인덱스
    let mid = Math.floor((min + max) / 2);
    // target이 중간값보다 작다면, max를 mid 바로 전으로 옮긴다.
    if (target < arr[mid]) max = mid - 1;
    // target이 중간값보다 크다면, min을 mid 바로 다음으로 옮긴다.
    else if (arr[mid] < target) min = mid + 1;
    // 중간값이 target이라면 해당 인덱스 값 반환
    else return mid;
  }
  return -1; // 데이터가 없으면 -1을 반환한다.
};

console.log(
  binarySearch([1, 5, 3, 7, 50, 23, 456, 678, 789, 1256, 4567, 111], 7891)
);