이진 탐색이란?

이진 탐색(Binary Search)이란 순서대로 하나씩 탐색하는 선형탐색과는 다르게 정렬되어있는 요소들을 반씩 제외하여 탐색하는 알고리즘을 의미합니다.

이미지 출처 https://blog.penjee.com/binary-vs-linear-search-animated-gifs

이진 탐색 특징

이진 탐색이라는 알고리즘을 실행하기 이전에 전제로 미리 정렬되어야 하는 조건이 있습니다.

그리고 범위를 통해 반씩 나누어 버리는 방식이기 때문에, 반이라는 기준이 되는 중간값(mid)와 범위에서 가장 처음이 되는 값(low) 그리고 범위에서 가장 마지막이 되는 값(high)이란 개념을 가지게 됩니다.

탐색하고자 하는 값(target)이 기준이 되는 중간값(mid)보다 크다면 범위 초기값(low)를 중간값 다음의 값으로 설정하고, 새롭게 정의된 범위 초기값과 기존 범위 마지막값을 기준으로 새로운 중간값을 설정해줍니다.

반대로, 탐색하고자 하는 값이 기준이 되는 중간값(mid)보다 작다면 범위 마지막(high)를 중간값 이전의 값으로 설정하고, 새롭게 정의된 범위 마지막 값과 기존 범위 초기값을 기준으로 새로운 중간값을 설정해줍니다.

만약 탐색하고자 하는 값이 중간값(mid)과 동일하다면, 탐색을 마칩니다.

이진 탐색 JavaScript 구현코드

// const arr = [1, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59]
// 만약 탐색할 배열의 요소들이 정렬되어 있지 않는 경우, 이진 탐색을 하기 전에 sort((a,b)=>a-b)로 정렬해야 됩니다.

function binarySearch(arr, target) {
  let low = 0;
  let high = arr.length - 1;

  while (low <= high) {
    let mid = parseInt((low + high) / 2);

    if (target === arr[mid]) {
      return true; // 탐색하고자 하는 값의 인덱스를 리턴하는 경우 return mid로 수정
    } else {
      if (target < arr[mid]) {
        high = mid - 1;
      } else {
        low = mid + 1;
      }
    }
  }
  return false; // 탐색하고자 하는 값이 없을 경우를 -1로 리턴하는 경우 return -1로 수정
}

// binarySearch(arr, 37) // true
// binarySearch(arr, 1) // true
// binarySearch(arr, 2) // false

이진 탐색의 장단점

• 탐색하고자 하는 배열의 요소들이 우선적으로 정렬되어야 합니다.
• 선형 탐색은 O(n) 시간복잡도가 소요되지만, 이진 탐색은 O(1)(가장 효율적일 때)에서 O(log n) (가장 비효율적일 때)만큼의 시간복잡도가 소요됩니다.
• 최악의 경우 한쪽으로 편향된 트리가 될 수 있습니다.
  (위의 예시에서 1을 탐색하는 경우, 선형탐색은 1번의 과정으로 탐색하지만, 이진탐색은 4번 반복하여 탐색하게 된다.)

이미지 출처 https://blog.penjee.com/binary-vs-linear-search-animated-gifs

• 이를 해결하기 위해 다음과 같은 자료구조를 이용할 수 있습니다.(AVL트리, 레드-블랙 트리)