[Algorithm] 이진 탐색 알고리즘

📌 Toy coplit - 해당하는 알고리즘이 있는지 구글링 먼저 해보기!

이진 탐색 알고리즘 검색하고 나무위키만 봤어도 금방 풀었을 문제인데, 혼자 트리 생성하고 메소드 구현하다 시간만 날렸다. 기록해두고 잊지 않아야겠다.

🧩 이진 탐색 알고리즘

실제로 트리를 구현할 필요는 없다. 개념적으로 BST 구조라는 것이 떠오른다면 해당 알고리즘을 사용하자. 정렬된 리스트에서 빠르게 특정 값을 검색하고자 할 때 사용할 수 있다.

1. 이진 탐색 알고리즘의 개념

아래 과정을 while문으로 반복하며 자료의 가운데 항목(mid)과 target을 비교한다.

• target과 같으면 바로 리턴
• target 보다 작으면 mid 기준 오른쪽 배열로 대상 범위를 좁히고 다시 탐색
• target 보다 크면 mid 기준 왼쪽 배열로 대상 범위를 좁히고 다시 탐색

2. 이진 탐색 알고리즘의 시간복잡도

• 단순 탐색의 시간복잡도 : 선형시간 O(N)
• 이진 탐색의 시간복잡도 : 로그시간 O(logN) (-> 매우 빠르다!!)

단순 탐색에 비해 매우 빠르게 데이터를 찾을 수 있지만, 데이터가 반드시 정렬되어 있어야 한다.
탐색 대상의 범위를 1/2로 줄여나가며 반복적으로 탐색한다.

3. 구현 코드 (javascript)

아래의 코드가 전형적인 코드 형식이므로 그대로 활용하면 된다.

const binarySearch = function (arr, target) {
  
  let start = 0;
  let end = arr.length - 1;

  while (start <= end) {
    let mid = Math.floor((start+end)/2);
    if (arr[mid] === target) {
      return mid;
    } else if (arr[mid] > target) {
      end = mid - 1;
    } else if (arr[mid] < target) {
      start = mid + 1;
    }
  }
  return -1;
};