JavaScript로 이진 탐색 구현하기 – 개념부터 구현까지 완벽 마스터

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

JavaScript로 이진 탐색 구현하기는 정렬된 배열에서 특정 값을 효율적으로 찾는 알고리즘입니다. 이진 탐색(Binary Search)은 탐색 범위를 절반씩 줄여가며 목표값을 찾는 분할 정복 알고리즘으로, 순차 탐색에 비해 월등히 빠른 성능을 보입니다. 코딩테스트와 실무에서 자주 사용되는 필수 알고리즘이며, 특히 대용량 데이터 처리 시 그 진가를 발휘합니다. 이진 탐색은 반드시 정렬된 배열에서만 동작하며, 이 조건이 충족되면 O(log n)의 탁월한 시간 복잡도로 원하는 값을 찾을 수 있습니다.

2. 이진 탐색의 동작 원리 상세 설명

이진 탐색은 ‘중간값 비교’를 핵심으로 동작합니다. 먼저 배열의 중간 인덱스를 계산하고, 중간값과 목표값을 비교합니다. 만약 중간값이 목표값과 일치하면 탐색을 종료하고 해당 인덱스를 반환합니다. 중간값이 목표값보다 크다면 목표값은 왼쪽 절반에 있으므로 탐색 범위를 왼쪽으로 좁힙니다. 반대로 중간값이 목표값보다 작다면 오른쪽 절반을 탐색합니다.

예를 들어 [1, 3, 5, 7, 9, 11, 13, 15, 17]에서 7을 찾는다고 가정해봅시다. 첫 번째 단계에서 중간값 9와 비교하면 7이 더 작으므로 왼쪽 부분 [1, 3, 5, 7]만 탐색합니다. 다시 중간값 3과 비교하면 7이 더 크므로 [5, 7]을 탐색하고, 최종적으로 7을 찾게 됩니다. 이처럼 매 단계마다 탐색 범위가 절반으로 줄어들기 때문에 매우 효율적입니다.

3. 시간 복잡도와 공간 복잡도 분석

시간 복잡도: 이진 탐색의 시간 복잡도는 O(log n)입니다. 매 단계마다 탐색 범위가 절반으로 줄어들기 때문에, n개의 요소가 있을 때 최대 log₂n번의 비교만 수행하면 됩니다. 예를 들어 1,000개의 요소에서는 최대 10번, 1,000,000개의 요소에서는 최대 20번만 비교하면 됩니다. 이는 순차 탐색의 O(n)에 비해 압도적으로 빠릅니다.

공간 복잡도: 반복문을 사용한 구현은 O(1)의 공간 복잡도를 가집니다. 추가 메모리 사용 없이 인덱스 변수만으로 구현 가능합니다. 재귀 방식은 호출 스택을 사용하므로 O(log n)의 공간 복잡도를 가지지만, 코드가 더 직관적입니다. 실무에서는 스택 오버플로우 위험이 없는 반복문 방식을 선호하는 경향이 있습니다.

4. JavaScript로 이진 탐색 단계별 구현 과정

4.1 반복문을 이용한 구현 (추천)

가장 기본적이고 효율적인 방법입니다. 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 sortedArray = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19];
console.log(binarySearch(sortedArray, 7));   // 3
console.log(binarySearch(sortedArray, 13));  // 6
console.log(binarySearch(sortedArray, 4));   // -1 (없음)

4.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);
  } else {
    return binarySearchRecursive(arr, target, mid + 1, right);
  }
}

// 사용 예제
const numbers = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20];
console.log(binarySearchRecursive(numbers, 10));  // 4
console.log(binarySearchRecursive(numbers, 16));  // 7

4.3 하한선/상한선 찾기 (Lower/Upper Bound)

중복된 값이 있을 때 첫 번째 또는 마지막 위치를 찾는 변형 알고리즘입니다.

// 목표값 이상인 첫 번째 인덱스 찾기 (Lower 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) {
      right = mid;
    } else {
      left = mid + 1;
    }
  }
  
  return left;
}

// 목표값 초과인 첫 번째 인덱스 찾기 (Upper Bound)
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) {
      right = mid;
    } else {
      left = mid + 1;
    }
  }
  
  return left;
}

// 사용 예제
const duplicates = [1, 2, 2, 2, 3, 4, 4, 5];
console.log(lowerBound(duplicates, 2));  // 1 (첫 번째 2의 위치)
console.log(upperBound(duplicates, 2));  // 4 (2를 초과하는 첫 위치)

5. 이진 탐색 최적화 방법

5.1 중간값 계산 시 오버플로우 방지

(left + right) / 2 대신 left + (right - left) / 2를 사용하면 큰 수에서 발생할 수 있는 오버플로우를 방지할 수 있습니다. JavaScript는 Number.MAX_SAFE_INTEGER까지 안전하지만, 다른 언어로 포팅할 때를 대비해 좋은 습관입니다.

5.2 비트 연산으로 성능 향상

// Math.floor 대신 비트 시프트 사용
const mid = left + ((right - left) >> 1);
// 또는
const mid = (left + right) >>> 1;  // 부호 없는 우측 시프트

5.3 조기 종료 조건 추가

배열이 비어있거나 목표값이 범위를 벗어난 경우 즉시 반환하여 불필요한 연산을 줄입니다.

function optimizedBinarySearch(arr, target) {
  // 조기 종료 조건
  if (arr.length === 0 || target < arr[0] || target > arr[arr.length - 1]) {
    return -1;
  }
  
  let left = 0;
  let right = arr.length - 1;
  
  while (left <= right) {
    const mid = left + ((right - left) >> 1);
    
    if (arr[mid] === target) return mid;
    if (arr[mid] > target) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
  
  return -1;
}

6. 실전 활용 예제

6.1 회전된 정렬 배열에서 탐색

function searchRotated(nums, target) {
  let left = 0;
  let right = nums.length - 1;
  
  while (left <= right) {
    const mid = Math.floor(left + (right - left) / 2);
    
    if (nums[mid] === target) return mid;
    
    // 왼쪽 부분이 정렬되어 있는 경우
    if (nums[left] <= nums[mid]) {
      if (nums[left] <= target && target < nums[mid]) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    } 
    // 오른쪽 부분이 정렬되어 있는 경우
    else {
      if (nums[mid] < target && target <= nums[right]) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
  }
  
  return -1;
}

console.log(searchRotated([4, 5, 6, 7, 0, 1, 2], 0));  // 4

6.2 제곱근 구하기 (정수 부분)

function mySqrt(x) {
  if (x < 2) return x;
  
  let left = 1;
  let right = Math.floor(x / 2);
  
  while (left <= right) {
    const mid = Math.floor(left + (right - left) / 2);
    const square = mid * mid;
    
    if (square === x) return mid;
    if (square > x) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
  
  return right;
}

console.log(mySqrt(8));  // 2 (2² = 4, 3² = 9)

6.3 첫 번째 잘못된 버전 찾기

function firstBadVersion(n, isBadVersion) {
  let left = 1;
  let right = n;
  
  while (left < right) {
    const mid = Math.floor(left + (right - left) / 2);
    
    if (isBadVersion(mid)) {
      right = mid;  // 더 이른 버전에도 오류가 있을 수 있음
    } else {
      left = mid + 1;
    }
  }
  
  return left;
}

마무리

JavaScript로 이진 탐색 구현하기는 알고리즘 학습의 핵심이며, 코딩테스트와 실무 모두에서 빈번하게 사용됩니다. 정렬된 데이터에서 O(log n)의 빠른 탐색이 필요할 때, 또는 파라메트릭 서치나 결정 문제를 해결할 때 이진 탐색이 최적의 선택입니다. 반복문 구현을 기본으로 익히고, 상황에 따라 재귀나 변형 알고리즘을 활용하세요. 중간값 계산 시 오버플로우 방지와 조기 종료 최적화를 적용하면 더욱 견고한 코드를 작성할 수 있습니다.