이진 탐색(Binary Search)

이진 탐색(Binary Search)

• 탐색할 범위를 축소해가며 원하는 값을 찾는 알고리즘
• 모든 탐색 범위를 전부 탐색하는 선형 탐색(Liner Search)보다 속도 면에서 빠르다는 장점
• 큌 정렬과 마찬가지로 분할과 정복 기법을 사용하기 때문에 시간 복잡도가 O(log2N) 엄청나게 빠른속도를 자랑
• 삽입, 삭제를 수행한 수에 항상 정렬된 배열에 대해서만 수행이 가능

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

구현

• Divide: 배열을 두 개의 서브 배열로 나눔
• Conquer
  • 검색할 숫자 > 중간값 => 뒷 부분 서브 리스트에서 검색할 숫자를 찾음
  • 검색할 숫자 < 중간값 => 앞 부분 서브 리스트에서 검색할 숫자를 찾음

// 이진 검색을 이용하여 target 값을 찾기

function binarySearch(target, searchArr) {
  const sortArr = searchArr.sort((a, b) => a - b);
  let min = 0;
  let max = sortArr.length - 1;
  let mid = Math.floor((min + max) / 2);

  if(!searchArr.length) return false;

  while (target !== sortArr[mid]) {
    if (target > sortArr[mid]) {
      min = mid + 1;
      mid = Math.floor((min + max) / 2);
    } else {
      min = mid - 1;
      mid = Math.floor((min + max) / 2);
    }
  }
  return sortArr[mid];
}

const searchArr = [9, 1, 5, 12, 4, 10, 3, 6, 7, 13, 15, 20];

console.log(binarySearch(12, searchArr));