Blog

이진 탐색 알고리즘 소개

JavaScript로 이진 탐색 구현하기는 정렬된 배열에서 특정 값을 효율적으로 찾는 대표적인 탐색 알고리즘입니다. 이진 탐색(Binary Search)은 탐색 범위를 절반씩 줄여가며 원하는 값을 찾는 방식으로, 선형 탐색보다 훨씬 빠른 성능을 제공합니다. 이 알고리즘은 코딩 테스트에서 자주 출제되며, 대용량 데이터 처리에서도 필수적으로 활용됩니다. 이진 탐색은 분할 정복(Divide and Conquer) 전략을 사용하여 문제를 해결하며, 정렬된 데이터에서만 사용할 수 있다는 제약이 있지만 그 효율성은 매우 뛰어납니다.

이진 탐색의 동작 원리

이진 탐색의 핵심 원리는 중간값과의 비교를 통한 탐색 범위 축소입니다. 알고리즘은 다음과 같은 단계로 진행됩니다:

1. 초기 설정: 배열의 시작 인덱스(left)와 끝 인덱스(right)를 설정합니다.
2. 중간값 계산: (left + right) / 2를 통해 중간 인덱스(mid)를 구합니다.
3. 비교 연산: 중간값이 찾고자 하는 값(target)과 같으면 해당 인덱스를 반환합니다.
4. 범위 조정: target이 중간값보다 작으면 right = mid – 1로 왼쪽 범위를 탐색하고, 크면 left = mid + 1로 오른쪽 범위를 탐색합니다.
5. 반복 또는 종료: left가 right보다 커지면 값이 존재하지 않는 것으로 판단하고 -1을 반환합니다.

이 과정에서 매 단계마다 탐색 범위가 절반으로 줄어들기 때문에 매우 효율적입니다. 예를 들어, 1000개의 요소가 있는 배열에서 최대 10번의 비교만으로 원하는 값을 찾을 수 있습니다.

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

시간 복잡도: 이진 탐색의 시간 복잡도는 O(log n)입니다. 매 단계마다 탐색 범위가 절반으로 줄어들기 때문에 로그 시간에 결과를 얻을 수 있습니다. n개의 요소에서 최악의 경우 log₂n번의 비교 연산이 필요합니다. 예를 들어, 100만 개의 요소가 있어도 약 20번의 비교면 충분합니다.

공간 복잡도: 반복문을 사용한 구현의 경우 O(1)의 상수 공간만 필요합니다. 재귀를 사용한 구현은 호출 스택으로 인해 O(log n)의 공간이 필요합니다. 일반적으로 반복문 방식이 메모리 효율성 면에서 더 유리합니다.

비교: 선형 탐색의 O(n)과 비교하면 이진 탐색은 대용량 데이터에서 압도적으로 빠릅니다. 하지만 데이터가 정렬되어 있어야 한다는 전제 조건이 있으므로, 정렬되지 않은 데이터는 먼저 정렬(O(n log n))해야 합니다.

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

1. 반복문을 이용한 이진 탐색 구현

가장 기본적이고 효율적인 방법은 while 반복문을 사용하는 것입니다:

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;
    }
    
    // target이 중간값보다 작으면 왼쪽 탐색
    if (arr[mid] > target) {
      right = mid - 1;
    } 
    // target이 중간값보다 크면 오른쪽 탐색
    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)

중복된 값이 있을 때 첫 번째 또는 마지막 위치를 찾는 변형:

// 첫 번째 위치 찾기 (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) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }
  
  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) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }
  
  return left;
}

const duplicates = [1, 2, 2, 2, 3, 4, 5];
console.log(lowerBound(duplicates, 2)); // 1 (첫 번째 2의 인덱스)
console.log(upperBound(duplicates, 2)); // 4 (마지막 2 다음 인덱스)

이진 탐색 최적화 방법

JavaScript로 이진 탐색 구현하기에서 성능을 더욱 향상시킬 수 있는 최적화 기법들입니다:

1. 오버플로우 방지

중간값 계산 시 (left + right) / 2 대신 left + (right - left) / 2를 사용하면 큰 수에서 발생할 수 있는 오버플로우를 방지할 수 있습니다. JavaScript는 Number.MAX_SAFE_INTEGER를 넘으면 정밀도 문제가 발생할 수 있습니다.

2. 비트 연산 활용

// Math.floor 대신 비트 연산 사용 (약간 더 빠름)
const mid = left + ((right - left) >> 1);

3. 조기 종료 조건

배열의 첫 번째/마지막 요소와 비교하여 탐색 범위를 벗어나면 즉시 -1을 반환합니다:

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

4. 캐싱 활용

동일한 배열에서 여러 번 검색할 때는 배열을 클래스로 래핑하여 메타데이터를 캐싱할 수 있습니다.

실전 활용 예제

회전된 정렬 배열에서 탐색

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

// 사용 예시: [4,5,6,7,0,1,2]에서 0 찾기
console.log(searchRotatedArray([4,5,6,7,0,1,2], 0)); // 4

제곱근 구하기

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

마무리

JavaScript로 이진 탐색 구현하기를 통해 효율적인 탐색 알고리즘의 핵심 원리를 배웠습니다. 이진 탐색은 O(log n)의 시간 복잡도로 대용량 데이터 처리에 필수적이며, 코딩 테스트에서도 자주 활용됩니다. 반복문과 재귀 두 가지 방식 모두 장단점이 있으므로 상황에 맞게 선택하세요. Lower Bound, Upper Bound 같은 변형 기법과 회전 배열 탐색 같은 응용 문제도 함께 익혀두면 실전에서 큰 도움이 됩니다. 정렬된 데이터에서 빠른 탐색이 필요할 때는 항상 이진 탐색을 먼저 고려하시기 바랍니다.