Blog

알고리즘 소개 및 개념

JavaScript로 이진 탐색 구현하기는 효율적인 검색 알고리즘을 배우는 핵심 과정입니다. 이진 탐색(Binary Search)은 정렬된 배열에서 특정 값을 찾는 알고리즘으로, 배열을 반으로 나누면서 탐색 범위를 좁혀가는 분할 정복 방식을 사용합니다. 선형 탐색이 O(n)의 시간이 걸리는 것과 달리, 이진 탐색은 O(log n)의 시간 복잡도로 매우 빠른 검색이 가능합니다. 대용량 데이터베이스 검색, 게임 개발, 최적화 문제 등 실무에서 광범위하게 활용되는 필수 알고리즘입니다.

동작 원리 상세 설명

이진 탐색의 핵심 원리는 ‘중간값 비교’입니다. 먼저 배열의 중간 인덱스를 계산하고, 중간값과 찾고자 하는 목표값을 비교합니다. 만약 중간값이 목표값보다 크다면 왼쪽 절반만 탐색하고, 작다면 오른쪽 절반만 탐색합니다. 이 과정을 반복하면 매번 탐색 범위가 절반으로 줄어들게 됩니다. 예를 들어, [1, 3, 5, 7, 9, 11, 13]에서 7을 찾는다면: 1단계에서 중간값 7을 찾아 바로 반환합니다. 9를 찾는다면: 중간값 7보다 크므로 오른쪽 [9, 11, 13]을 탐색하고, 다시 중간값 11보다 작으므로 [9]를 탐색하여 찾습니다. 이처럼 매 단계마다 탐색 공간을 절반으로 줄이는 것이 이진 탐색의 핵심입니다. 단, 반드시 배열이 정렬되어 있어야 한다는 전제조건이 필요합니다.

시간/공간 복잡도 분석

시간 복잡도: 이진 탐색의 최선의 경우는 O(1)입니다. 첫 번째 비교에서 바로 목표값을 찾는 경우입니다. 평균과 최악의 경우는 O(log n)으로, n개의 요소를 가진 배열에서 최대 log₂n번의 비교만 수행합니다. 예를 들어 1,000,000개의 요소는 최대 20번, 1,000,000,000개는 30번의 비교로 찾을 수 있습니다. 공간 복잡도: 반복문으로 구현하면 O(1)의 상수 공간만 사용합니다. 재귀로 구현할 경우 호출 스택 때문에 O(log n)의 공간이 필요합니다. 대용량 데이터를 다룰 때는 반복문 방식이 메모리 효율면에서 더 유리합니다. 선형 탐색 O(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) {
      right = mid - 1;
    } 
    // 목표값이 중간값보다 크면 오른쪽 탐색
    else {
      left = 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, left, mid - 1);
  } else {
    return binarySearchRecursive(arr, target, mid + 1, right);
  }
}

// 사용 예시
const numbers = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20];
console.log(binarySearchRecursive(numbers, 12)); // 5
console.log(binarySearchRecursive(numbers, 15)); // -1

3. 경계값 찾기 (Lower Bound / Upper Bound)

// 목표값 이상의 첫 번째 인덱스 찾기
function lowerBound(arr, target) {
  let left = 0;
  let right = arr.length;
  
  while (left < right) {
    const mid = Math.floor(left + (right - left) / 2);
    
    if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }
  
  return left;
}

// 목표값 초과의 첫 번째 인덱스 찾기
function upperBound(arr, target) {
  let left = 0;
  let right = arr.length;
  
  while (left < right) {
    const mid = Math.floor(left + (right - left) / 2);
    
    if (arr[mid] <= target) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }
  
  return left;
}

최적화 방법

1. 오버플로우 방지: 중간 인덱스 계산 시 (left + right) / 2 대신 left + (right - left) / 2를 사용하여 정수 오버플로우를 방지합니다. 2. 비트 연산 활용: Math.floor(mid) 대신 (left + right) >> 1을 사용하면 약간의 성능 향상이 가능합니다. 3. 조기 종료: 배열 크기가 작을 때는 선형 탐색이 더 빠를 수 있으므로, 임계값(예: 10개 이하)에서는 선형 탐색으로 전환합니다. 4. 캐싱 전략: 자주 탐색하는 배열은 인덱스 맵을 미리 생성하여 O(1) 조회를 구현할 수 있습니다. 5. 병렬 처리: 여러 개의 값을 찾을 때는 배치 처리로 캐시 효율성을 높일 수 있습니다.

실전 활용 예제

// 실전 예제: 게임 점수 랭킹 시스템
class RankingSystem {
  constructor() {
    this.scores = []; // 내림차순 정렬된 점수 배열
  }
  
  // 특정 점수의 순위 찾기
  findRank(score) {
    let left = 0;
    let right = this.scores.length;
    
    while (left < right) {
      const mid = Math.floor(left + (right - left) / 2);
      
      if (this.scores[mid] > score) {
        left = mid + 1;
      } else {
        right = mid;
      }
    }
    
    return left + 1; // 순위는 1부터 시작
  }
  
  // 점수 삽입 (정렬 유지)
  insertScore(score) {
    const rank = this.findRank(score);
    this.scores.splice(rank - 1, 0, score);
  }
}

// 사용 예시
const ranking = new RankingSystem();
ranking.scores = [950, 870, 820, 750, 680, 590];
console.log(ranking.findRank(800)); // 4위
ranking.insertScore(800);
console.log(ranking.scores); // [950, 870, 820, 800, 750, 680, 590]

주의사항 및 팁

• 정렬 필수: 이진 탐색은 반드시 정렬된 배열에서만 동작합니다. 정렬되지 않은 배열에 사용하면 잘못된 결과가 나옵니다.
• 중복값 처리: 중복값이 있을 때 첫 번째/마지막 인덱스를 찾으려면 Lower Bound/Upper Bound 알고리즘을 사용해야 합니다.
• 빈 배열 처리: 배열이 비어있거나 null인 경우를 처리하는 예외 처리 로직을 추가하세요.
• 부동소수점 비교: 실수 배열에서는 정확한 비교를 위해 epsilon 값을 사용한 근사 비교가 필요할 수 있습니다.

마무리

JavaScript로 이진 탐색 구현하기를 통해 효율적인 검색 알고리즘의 핵심을 마스터했습니다. 이진 탐색은 코딩 테스트에서 자주 출제되며, 실무에서도 성능 최적화의 핵심 도구입니다. 반복문과 재귀 방식을 모두 이해하고, 상황에 맞게 선택할 수 있어야 합니다. 이제 다양한 문제에 이진 탐색을 적용해보며 실력을 향상시켜보세요. 정렬된 데이터를 다룰 때마다 이진 탐색을 고려하는 습관을 들이면, 알고리즘 문제 해결 능력이 크게 향상될 것입니다.