이진 탐색 (Binary Search)

이진 탐색이란?

정렬된 배열에서 특정 값을 찾을 때, 매번 탐색 범위를 반으로 줄여가며 효율적으로 찾는 알고리즘이다.

배열: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
찾는 값: 7

1단계: 중간값 5와 비교 → 7 > 5, 오른쪽 범위로
2단계: 중간값 8과 비교 → 7 < 8, 왼쪽 범위로
3단계: 중간값 7과 비교 → 7 == 7, 찾음!

선형 탐색이 O(n)인 반면, 이진 탐색은 O(log n)의 시간복잡도를 가진다.

 

동작 원리

1. 배열의 중간 값을 확인
2. 찾는 값과 중간 값을 비교
   • 같으면 → 탐색 성공
   • 크면 → 오른쪽 절반에서 탐색
   • 작으면 → 왼쪽 절반에서 탐색
3. 범위가 없어질 때까지 반복

 

장단점

장점

• 빠른 탐색 속도: O(log n)
• 대용량 데이터에서도 효율적

단점

• 배열이 정렬되어 있어야 함
• 삽입/삭제 후 재정렬 필요
• 정렬되지 않은 데이터에는 사용 불가

 

구현

재귀 방식

function binarySearch(arr, target, start, end) {
  if (start > end) {
    return null; // 탐색 실패
  }

  let mid = Math.floor((start + end) / 2);

  if (arr[mid] === target) {
    return mid; // 찾음
  } else if (target > arr[mid]) {
    return binarySearch(arr, target, mid + 1, end); // 오른쪽 탐색
  } else {
    return binarySearch(arr, target, start, mid - 1); // 왼쪽 탐색
  }
}

 

사용 예제

let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
let index = binarySearch(arr, 7, 0, arr.length - 1);
console.log(index); // 6

 

시간 복잡도

경우	시간 복잡도
최선	O(1) - 중간값이 바로 찾는 값
평균	O(log n)
최악	O(log n) - 끝까지 탐색

 

이진 탐색의 한계와 해결책

이진 탐색은 정렬된 배열에만 사용할 수 있다는 한계가 있다.

데이터가 자주 변경되는 상황에서는:

• 삽입/삭제마다 정렬 필요 → O(n)
• 전체 성능 저하

이 문제를 해결하는 자료구조가 바로 이진 탐색 트리(BST)다.
BST는 데이터 삽입 시 자동으로 정렬 상태를 유지하며, 탐색/삽입/삭제 모두 O(log n)의 성능을 제공한다.