Blog

JavaScript로 이진 탐색 구현하기 – 효율적인 검색 알고리즘 완벽 가이드

JavaScript로 이진 탐색 구현하기는 정렬된 배열에서 특정 값을 빠르게 찾는 효율적인 알고리즘입니다. 이진 탐색(Binary Search)은 선형 탐색보다 훨씬 빠른 검색 속도를 자랑하며, 대규모 데이터셋을 다룰 때 필수적인 알고리즘입니다. 이 가이드에서는 이진 탐색의 개념부터 실전 구현까지 상세하게 다루어 코딩 테스트와 실무에서 활용할 수 있도록 도와드리겠습니다.

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

이진 탐색은 정렬된 배열에서 특정 값을 찾는 대표적인 분할 정복(Divide and Conquer) 알고리즘입니다. 배열의 중간 값을 기준으로 찾고자 하는 값이 왼쪽에 있는지 오른쪽에 있는지 판단하여, 검색 범위를 절반씩 줄여나가는 방식으로 동작합니다.

예를 들어, 1부터 100까지의 숫자 중에서 특정 숫자를 맞추는 게임을 한다고 가정해봅시다. 선형 탐색은 1부터 순차적으로 확인하지만, 이진 탐색은 50을 먼저 확인하고, 답이 더 크면 51~100 범위에서, 작으면 1~49 범위에서 다시 중간값을 확인하는 방식입니다. 이러한 방식으로 매번 검색 범위를 절반으로 줄이기 때문에 매우 효율적입니다.

이진 탐색의 전제 조건은 배열이 반드시 정렬되어 있어야 한다는 점입니다. 정렬되지 않은 배열에서는 이진 탐색을 사용할 수 없으므로, 먼저 정렬 작업이 필요합니다.

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

JavaScript로 이진 탐색 구현하기의 핵심 원리를 단계별로 살펴보겠습니다.

동작 과정:

1. 초기 설정: 배열의 시작 인덱스(left)를 0으로, 끝 인덱스(right)를 배열 길이 – 1로 설정합니다.
2. 중간값 계산: 중간 인덱스(mid)를 계산합니다. mid = Math.floor((left + right) / 2)
3. 값 비교: 중간 인덱스의 값과 찾고자 하는 값을 비교합니다.
   • 중간값이 찾는 값과 같으면 해당 인덱스를 반환합니다.
   • 중간값이 찾는 값보다 크면, 오른쪽 범위는 버리고 왼쪽 범위에서 다시 탐색합니다. (right = mid – 1)
   • 중간값이 찾는 값보다 작으면, 왼쪽 범위는 버리고 오른쪽 범위에서 다시 탐색합니다. (left = mid + 1)
4. 반복: left가 right보다 커질 때까지 2-3 과정을 반복합니다.
5. 종료: 값을 찾으면 인덱스를 반환하고, 찾지 못하면 -1을 반환합니다.

예시: 정렬된 배열 [1, 3, 5, 7, 9, 11, 13, 15]에서 7을 찾는 과정

• 1단계: left=0, right=7, mid=3, arr[3]=7 → 찾았으므로 인덱스 3 반환

예시: 같은 배열에서 11을 찾는 과정

• 1단계: left=0, right=7, mid=3, arr[3]=7 < 11 → left=4
• 2단계: left=4, right=7, mid=5, arr[5]=11 → 찾았으므로 인덱스 5 반환

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

시간 복잡도:

• 최선의 경우 (Best Case): O(1) – 첫 번째 비교에서 중간값이 찾는 값인 경우
• 평균 및 최악의 경우 (Average/Worst Case): O(log n) – 매번 검색 범위가 절반으로 줄어들기 때문

n개의 요소가 있는 배열에서 이진 탐색은 최대 log₂n번의 비교만으로 결과를 찾을 수 있습니다. 예를 들어, 1,000개의 요소가 있다면 최대 10번, 1,000,000개의 요소가 있다면 최대 20번의 비교만 필요합니다. 이는 선형 탐색의 O(n)과 비교하면 엄청난 성능 향상입니다.

공간 복잡도:

• 반복문 방식: O(1) – 추가 메모리 사용 없이 인덱스 변수만 사용
• 재귀 방식: O(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, 11)); // 출력: 5
console.log(binarySearch(sortedArray, 6));  // 출력: -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, mid + 1, right);
  }
  
  // 중간값이 타겟보다 크면 왼쪽 절반에서 재귀 호출
  return binarySearchRecursive(arr, target, left, mid - 1);
}

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

4.3 첫 번째 인덱스 찾기 (Lower Bound)

중복된 값이 있을 때 가장 왼쪽(첫 번째) 인덱스를 찾는 구현입니다.

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

// 사용 예시
const arrayWithDuplicates = [1, 2, 2, 2, 3, 4, 5, 5, 5, 6];
console.log(binarySearchFirst(arrayWithDuplicates, 2)); // 출력: 1 (첫 번째 2의 위치)
console.log(binarySearchFirst(arrayWithDuplicates, 5)); // 출력: 6 (첫 번째 5의 위치)

4.4 마지막 인덱스 찾기 (Upper Bound)

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

// 사용 예시
console.log(binarySearchLast(arrayWithDuplicates, 2)); // 출력: 3 (마지막 2의 위치)
console.log(binarySearchLast(arrayWithDuplicates, 5)); // 출력: 8 (마지막 5의 위치)

5. 최적화 방법 및 주의사항

5.1 오버플로우 방지

중간 인덱스를 계산할 때 (left + right) / 2 대신 left + (right - left) / 2를 사용하면 큰 숫자에서 발생할 수 있는 오버플로우를 방지할 수 있습니다. JavaScript는 자동으로 큰 숫자를 처리하지만, 다른 언어로 이식할 때를 대비해 안전한 방식을 사용하는 것이 좋습니다.

5.2 비트 연산자 활용

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

5.3 경계 조건 처리

function binarySearchOptimized(arr, target) {
  // 빈 배열 처리
  if (arr.length === 0) return -1;
  
  // 범위 밖 값 빠른 체크
  if (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) left = mid + 1;
    else right = mid - 1;
  }
  
  return -1;
}

5.4 객체 배열에서의 이진 탐색

function binarySearchObjects(arr, target, key) {
  let left = 0;
  let right = arr.length - 1;
  
  while (left <= right) {
    const mid = Math.floor(left + (right - left) / 2);
    const midValue = arr[mid][key];
    
    if (midValue === target) return mid;
    if (midValue < target) left = mid + 1;
    else right = mid - 1;
  }
  
  return -1;
}

// 사용 예시
const users = [
  { id: 1, name: 'Alice' },
  { id: 5, name: 'Bob' },
  { id: 10, name: 'Charlie' },
  { id: 15, name: 'David' }
];

console.log(binarySearchObjects(users, 10, 'id')); // 출력: 2

6. 실전 활용 예제

예제 1: 정렬된 배열에서 특정 값의 개수 구하기

function countOccurrences(arr, target) {
  const first = binarySearchFirst(arr, target);
  if (first === -1) return 0;
  
  const last = binarySearchLast(arr, target);
  return last - first + 1;
}

const numbers = [1, 2, 2, 2, 3, 4, 5, 5, 5, 6];
console.log(countOccurrences(numbers, 2)); // 출력: 3
console.log(countOccurrences(numbers, 5)); // 출력: 3

예제 2: 회전된 정렬 배열에서 최솟값 찾기

function findMinInRotatedArray(arr) {
  let left = 0;
  let right = arr.length - 1;
  
  while (left < right) {
    const mid = Math.floor(left + (right - left) / 2);
    
    if (arr[mid] > arr[right]) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }
  
  return arr[left];
}

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

예제 3: 삽입 위치 찾기 (LeetCode 스타일)

function searchInsertPosition(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 left; // 삽입될 위치
}

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

마무리

JavaScript로 이진 탐색 구현하기를 통해 효율적인 검색 알고리즘을 마스터했습니다. 이진 탐색은 O(log n)의 시간 복잡도로 대규모 데이터에서도 빠른 검색이 가능하며, 코딩 테스트와 실무에서 자주 활용되는 필수 알고리즘입니다. 반복문과 재귀 방식 모두 이해하고, 다양한 변형 문제를 풀어보면서 실력을 향상시켜보세요. 정렬된 데이터를 다룰 때는 항상 이진 탐색을 먼저 고려하는 습관을 들이시기 바랍니다!