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

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

JavaScript로 이진 탐색 구현하기는 정렬된 배열에서 특정 값을 효율적으로 찾는 핵심 알고리즘입니다. 이진 탐색(Binary Search)은 탐색 범위를 절반씩 줄여가며 원하는 값을 찾는 분할 정복 알고리즘으로, 선형 탐색에 비해 훨씬 빠른 성능을 제공합니다.

이진 탐색의 핵심 아이디어는 정렬된 데이터의 중간값과 찾고자 하는 값을 비교하여, 탐색 범위를 절반으로 줄이는 것입니다. 만약 중간값이 찾는 값보다 크다면 왼쪽 절반을, 작다면 오른쪽 절반을 탐색합니다. 이 과정을 반복하여 값을 찾거나 탐색 범위가 없어질 때까지 진행합니다. 이 알고리즘은 코딩 테스트에서 자주 출제되며, 실무에서도 대용량 데이터 처리에 필수적입니다.

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

이진 탐색의 동작 원리를 구체적으로 살펴보겠습니다. 예를 들어, [1, 3, 5, 7, 9, 11, 13, 15] 배열에서 값 7을 찾는다고 가정해봅시다.

1단계: 배열의 시작 인덱스(0)와 끝 인덱스(7)를 설정합니다. 중간 인덱스는 (0 + 7) / 2 = 3이며, 중간값은 7입니다. 찾는 값과 일치하므로 탐색이 종료됩니다.

다른 예로, 값 11을 찾는 경우를 살펴봅시다.

1단계: 시작(0), 끝(7), 중간(3), 중간값(7). 11 > 7이므로 오른쪽 절반을 탐색합니다.

2단계: 시작(4), 끝(7), 중간(5), 중간값(11). 찾는 값과 일치하여 인덱스 5를 반환합니다.

만약 배열에 없는 값을 찾는다면, 시작 인덱스가 끝 인덱스보다 커지는 순간 탐색이 종료되며 -1을 반환합니다. 이렇게 매 단계마다 탐색 범위가 절반으로 줄어들기 때문에 매우 효율적입니다. 핵심은 정렬된 배열에서만 작동한다는 점입니다.

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

시간 복잡도:

• 최선의 경우: O(1) – 첫 번째 비교에서 중간값이 찾는 값과 일치하는 경우
• 평균/최악의 경우: O(log n) – 매 단계마다 탐색 범위가 절반으로 줄어듭니다. n개의 요소를 가진 배열에서 최대 log₂n번의 비교가 필요합니다.

예를 들어, 1024개의 요소를 가진 배열에서는 최대 10번의 비교만으로 원하는 값을 찾을 수 있습니다(2¹⁰ = 1024). 선형 탐색의 O(n)과 비교하면 엄청난 성능 차이를 보입니다.

공간 복잡도:

• 반복문 방식: O(1) – 추가적인 메모리 공간이 거의 필요하지 않습니다.
• 재귀 방식: O(log n) – 재귀 호출 스택에 최대 log n개의 프레임이 쌓입니다.

대용량 데이터를 처리할 때는 공간 효율성을 고려하여 반복문 방식을 선호합니다.

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

4.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

4.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 numbers = [2, 4, 6, 8, 10, 12, 14, 16];
console.log(binarySearchRecursive(numbers, 10)); // 출력: 4

4.3 구현 시 주의사항

• 중간 인덱스 계산: Math.floor((left + right) / 2) 대신 Math.floor(left + (right - left) / 2)를 사용하여 큰 숫자에서 오버플로우를 방지합니다.
• 경계 조건: left <= right 조건을 정확히 설정해야 합니다. <를 사용하면 특정 경우를 놓칠 수 있습니다.
• 정렬 확인: 이진 탐색은 정렬된 배열에서만 올바르게 작동합니다.

5. 이진 탐색 최적화 방법

5.1 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;
}

// Upper Bound: target 초과 값이 처음 나오는 위치
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;
}

5.2 중복 값 처리

중복된 값이 있는 배열에서 첫 번째 또는 마지막 인덱스를 찾을 때 Lower Bound와 Upper Bound를 활용할 수 있습니다. 이를 통해 특정 값의 개수를 upperBound(arr, target) - lowerBound(arr, target)으로 O(log n) 시간에 계산할 수 있습니다.

6. 실전 활용 예제

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

function searchRotatedArray(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[left] <= arr[mid]) {
      if (target >= arr[left] && target < arr[mid]) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    } 
    // 오른쪽 부분이 정렬되어 있는 경우
    else {
      if (target > arr[mid] && target <= arr[right]) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
  }
  return -1;
}

console.log(searchRotatedArray([4, 5, 6, 7, 0, 1, 2], 0)); // 출력: 4

6.2 제곱근 구하기

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

console.log(sqrt(16)); // 출력: 4

마무리

JavaScript로 이진 탐색 구현하기를 마스터하면 코딩 테스트와 실무에서 큰 도움이 됩니다. 정렬된 데이터에서 O(log n)의 시간 복잡도로 빠르게 탐색할 수 있으며, Lower Bound, Upper Bound 등의 변형을 통해 다양한 문제를 해결할 수 있습니다. 반복 연습을 통해 이진 탐색의 원리를 완벽히 이해하고, 실전에서 자유롭게 활용해보시기 바랍니다.