Blog

이진 탐색 알고리즘 소개

JavaScript로 이진 탐색 구현하기는 효율적인 검색 알고리즘을 익히는 데 필수적인 과정입니다. 이진 탐색(Binary Search)은 정렬된 배열에서 특정 값을 찾을 때 사용하는 알고리즘으로, 탐색 범위를 절반씩 줄여가며 목표 값을 찾습니다. 선형 탐색과 달리 O(log n)의 시간 복잡도를 가지므로 대용량 데이터에서 매우 효율적입니다. 코딩 테스트와 실무에서 자주 활용되며, 분할 정복(Divide and Conquer) 패러다임의 대표적인 예시입니다.

이진 탐색의 동작 원리

이진 탐색은 정렬된 배열의 중간 요소를 기준으로 탐색 범위를 좁혀가는 방식으로 동작합니다. 먼저 배열의 중간 인덱스를 계산하고, 중간 값과 찾고자 하는 목표 값을 비교합니다. 만약 중간 값이 목표 값보다 크다면 왼쪽 절반만 탐색하고, 작다면 오른쪽 절반만 탐색합니다. 이 과정을 목표 값을 찾거나 탐색 범위가 없어질 때까지 반복합니다.

예를 들어 [1, 3, 5, 7, 9, 11, 13, 15, 17, 19] 배열에서 7을 찾는다고 가정해봅시다. 첫 번째 단계에서 중간 값 9와 비교하여 7이 더 작으므로 왼쪽 절반 [1, 3, 5, 7, 9]를 탐색합니다. 두 번째 단계에서는 중간 값 5와 비교하여 7이 더 크므로 오른쪽 [7, 9]를 탐색합니다. 세 번째 단계에서 중간 값 7과 목표 값이 일치하여 탐색을 종료합니다. 이처럼 각 단계마다 탐색 범위가 절반으로 줄어들어 효율적인 검색이 가능합니다.

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

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

공간 복잡도는 구현 방식에 따라 달라집니다. 반복문을 사용한 구현은 O(1)의 공간 복잡도를 가지며, 재귀를 사용한 구현은 호출 스택으로 인해 O(log n)의 공간 복잡도를 가집니다. 실무에서는 메모리 효율성을 위해 반복문 방식을 선호하는 경우가 많습니다. 단, 이진 탐색은 반드시 정렬된 배열에서만 사용할 수 있다는 제약이 있으므로, 정렬되지 않은 데이터라면 먼저 정렬 과정이 필요합니다.

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

1. 반복문을 이용한 구현

가장 기본적이고 효율적인 방법은 while 반복문을 사용하는 것입니다. 왼쪽 포인터(left)와 오른쪽 포인터(right)를 설정하고, 중간 인덱스를 계산하며 범위를 좁혀갑니다.

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 numbers = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19];
console.log(binarySearch(numbers, 7));  // 3
console.log(binarySearch(numbers, 10)); // -1

2. 재귀를 이용한 구현

재귀적 접근은 코드가 더 간결하고 이해하기 쉽지만, 호출 스택을 사용하므로 메모리를 더 소비합니다.

function binarySearchRecursive(arr, target, left = 0, right = arr.length - 1) {
  // 기저 조건: 탐색 범위가 유효하지 않으면 -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);
  }
  
  // 목표 값이 중간 값보다 크면 오른쪽 절반 재귀 탐색
  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. 첫 번째/마지막 위치 찾기

중복된 값이 있는 배열에서 특정 값의 첫 번째 또는 마지막 위치를 찾는 변형 구현입니다.

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) {
      right = mid - 1;
    } else {
      left = 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) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
  
  return result;
}

// 사용 예시
const duplicates = [1, 2, 2, 2, 3, 4, 5];
console.log(findFirstPosition(duplicates, 2)); // 1
console.log(findLastPosition(duplicates, 2));  // 3

최적화 방법 및 고급 테크닉

1. 중간 인덱스 계산 최적화: Math.floor((left + right) / 2) 대신 Math.floor(left + (right – left) / 2)를 사용하면 매우 큰 배열에서 발생할 수 있는 정수 오버플로우를 방지할 수 있습니다.

2. 비교 횟수 최소화: 삼항 연산자나 조기 반환(early return)을 활용하여 불필요한 비교를 줄일 수 있습니다.

3. Lower Bound / Upper Bound 구현: 목표 값 이상의 첫 번째 요소 또는 목표 값을 초과하는 첫 번째 요소를 찾는 변형을 구현하면 더 다양한 문제에 활용할 수 있습니다.

// Lower Bound: target 이상의 첫 번째 인덱스
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;
}

4. TypeScript 타입 안전성: 제네릭을 활용하여 타입 안전한 이진 탐색 함수를 구현할 수 있습니다.

실전 활용 예제

JavaScript로 이진 탐색 구현하기 기법은 다양한 실전 문제에 활용됩니다. 대표적으로 회전된 정렬 배열에서 원소 찾기, 범위 내 개수 세기, 최솟값/최댓값 찾기 등의 문제가 있습니다.

// 실전 예제: 특정 범위 내 개수 세기
function countInRange(arr, lower, upper) {
  const lowerIdx = lowerBound(arr, lower);
  const upperIdx = lowerBound(arr, upper + 1);
  return upperIdx - lowerIdx;
}

const sortedArray = [1, 2, 4, 4, 5, 7, 8, 9];
console.log(countInRange(sortedArray, 4, 7)); // 4 (요소: 4, 4, 5, 7)

이진 탐색은 검색뿐만 아니라 파라메트릭 서치(Parametric Search), 결정 문제 등 다양한 알고리즘 패턴의 기초가 됩니다. 정렬된 데이터에서 효율적인 검색이 필요할 때마다 이진 탐색을 고려해보세요.