Blog

이진 탐색 알고리즘 소개

JavaScript로 이진 탐색 구현하기는 효율적인 검색 알고리즘을 학습하는 데 있어 가장 기본적이면서도 중요한 주제입니다. 이진 탐색(Binary Search)은 정렬된 배열에서 특정 값을 찾을 때 사용하는 알고리즘으로, 검색 범위를 절반씩 줄여나가며 탐색합니다. 선형 탐색과 달리 O(log n)의 시간 복잡도를 가지므로 대용량 데이터에서도 빠른 검색이 가능합니다. 코딩 테스트와 실무에서 자주 활용되는 필수 알고리즘이며, 다양한 응용 문제의 기초가 되므로 반드시 숙지해야 합니다.

이진 탐색의 동작 원리

이진 탐색은 분할 정복(Divide and Conquer) 전략을 사용합니다. 먼저 배열의 중간 요소를 선택하여 찾고자 하는 값과 비교합니다. 만약 중간 값이 찾는 값과 같다면 탐색을 종료하고, 중간 값이 찾는 값보다 크다면 왼쪽 절반을, 작다면 오른쪽 절반을 새로운 탐색 범위로 설정합니다.

예를 들어, [1, 3, 5, 7, 9, 11, 13, 15] 배열에서 7을 찾는다고 가정해봅시다. 첫 번째 단계에서 중간 값 7을 확인하고 바로 찾게 됩니다. 만약 11을 찾는다면 중간 값 7보다 크므로 오른쪽 절반 [9, 11, 13, 15]를 탐색하고, 다시 중간 값 11을 확인하여 찾게 됩니다. 이처럼 매 단계마다 탐색 범위가 절반으로 줄어들어 효율적인 검색이 가능합니다. 이진 탐색의 핵심은 배열이 반드시 정렬되어 있어야 한다는 점입니다.

시간 복잡도 및 공간 복잡도 분석

시간 복잡도: 이진 탐색의 시간 복잡도는 O(log n)입니다. 매 단계마다 탐색 범위가 절반으로 줄어들기 때문에, n개의 요소를 가진 배열에서 최대 log₂n번의 비교만으로 결과를 찾을 수 있습니다. 예를 들어 1,000개의 요소에서는 최대 10번, 1,000,000개에서는 약 20번의 비교만 필요합니다. 반면 선형 탐색은 O(n)의 시간 복잡도를 가지므로, 데이터가 많을수록 이진 탐색의 성능 우위가 두드러집니다.

공간 복잡도: 반복문을 사용한 구현은 O(1)의 공간 복잡도를 가집니다. 추가 메모리를 거의 사용하지 않기 때문입니다. 재귀를 사용한 구현은 O(log n)의 공간 복잡도를 가지는데, 이는 재귀 호출 스택에 최대 log n개의 함수 호출이 쌓이기 때문입니다. 일반적으로 반복문 방식이 메모리 효율면에서 더 유리합니다.

JavaScript로 이진 탐색 구현하기 – 단계별 구현

1. 반복문을 이용한 구현

반복문 방식은 스택 오버플로우 위험이 없고 메모리 효율이 좋아 실무에서 더 선호됩니다.

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  
  while (left <= right) {
    // 중간 인덱스 계산 (오버플로우 방지)
    const mid = Math.floor(left + (right - left) / 2);
    
    // 찾는 값을 발견한 경우
    if (arr[mid] === target) {
      return mid;
    }
    
    // 중간 값이 타겟보다 작으면 오른쪽 탐색
    if (arr[mid] < target) {
      left = mid + 1;
    } else {
      // 중간 값이 타겟보다 크면 왼쪽 탐색
      right = mid - 1;
    }
  }
  
  // 찾지 못한 경우
  return -1;
}

// 사용 예제
const sortedArray = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19];
console.log(binarySearch(sortedArray, 7));  // 3
console.log(binarySearch(sortedArray, 10)); // -1

2. 재귀를 이용한 구현

재귀 방식은 코드가 간결하고 이해하기 쉽지만, 깊은 재귀로 인한 스택 오버플로우 가능성이 있습니다.

function binarySearchRecursive(arr, target, left = 0, right = arr.length - 1) {
  // 기저 조건: 탐색 범위가 유효하지 않음
  if (left > right) {
    return -1;
  }
  
  const mid = Math.floor(left + (right - left) / 2);
  
  // 찾는 값을 발견한 경우
  if (arr[mid] === target) {
    return mid;
  }
  
  // 재귀 호출
  if (arr[mid] < target) {
    return binarySearchRecursive(arr, target, mid + 1, right);
  } else {
    return binarySearchRecursive(arr, target, left, mid - 1);
  }
}

// 사용 예제
const sortedArray = [2, 4, 6, 8, 10, 12, 14, 16];
console.log(binarySearchRecursive(sortedArray, 10)); // 4
console.log(binarySearchRecursive(sortedArray, 5));  // -1

3. 변형: 첫 번째/마지막 위치 찾기

중복된 값이 있을 때 첫 번째 또는 마지막 위치를 찾는 응용 구현입니다.

function findFirstPosition(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  let result = -1;
  
  while (left <= right) {
    const mid = Math.floor(left + (right - left) / 2);
    
    if (arr[mid] === target) {
      result = mid;
      right = mid - 1; // 왼쪽 계속 탐색
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  
  return result;
}

function findLastPosition(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  let result = -1;
  
  while (left <= right) {
    const mid = Math.floor(left + (right - left) / 2);
    
    if (arr[mid] === target) {
      result = mid;
      left = mid + 1; // 오른쪽 계속 탐색
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  
  return result;
}

최적화 방법 및 주의사항

1. 중간 인덱스 계산 최적화: Math.floor((left + right) / 2) 대신 Math.floor(left + (right - left) / 2)를 사용하면 매우 큰 배열에서 발생할 수 있는 정수 오버플로우를 방지할 수 있습니다. JavaScript는 Number 타입이 충분히 크지만, 다른 언어로 이식할 때를 고려한 좋은 습관입니다.

2. 정렬 확인: 이진 탐색은 정렬된 배열에서만 동작합니다. 정렬되지 않은 배열에 적용하면 잘못된 결과를 반환하므로, 필요시 사전에 배열을 정렬해야 합니다.

3. 경계 조건 처리: 빈 배열, 단일 요소 배열, 타겟이 범위를 벗어난 경우 등 엣지 케이스를 철저히 테스트해야 합니다.

4. 비교 함수 커스터마이징: 객체 배열이나 특수한 비교 로직이 필요한 경우, 비교 함수를 매개변수로 받아 유연하게 처리할 수 있습니다.

실전 활용 예제

JavaScript로 이진 탐색 구현하기 지식은 다양한 실전 문제에 응용됩니다. 코딩 테스트에서는 특정 값의 위치 찾기, 범위 내 개수 세기, 최적값 찾기 등의 문제가 자주 출제됩니다. 예를 들어 "정렬된 배열에서 특정 값 이상이 처음 나타나는 위치 찾기", "회전된 정렬 배열에서 최솟값 찾기" 등이 있습니다. 실무에서는 대용량 데이터베이스 인덱스 검색, 캐시 시스템, 게임의 스코어보드 검색 등에 활용됩니다. 또한 이진 탐색의 원리는 이진 탐색 트리(BST), 파라메트릭 서치 등 고급 알고리즘의 기초가 되므로 확실히 익혀두는 것이 중요합니다.