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

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

JavaScript로 이진 탐색 구현하기는 효율적인 검색 알고리즘을 마스터하는 핵심 과정입니다. 이진 탐색(Binary Search)은 정렬된 배열에서 특정 값을 찾는 가장 효율적인 알고리즘 중 하나로, 탐색 범위를 절반씩 줄여가며 목표 값을 찾습니다. 선형 탐색이 배열의 모든 요소를 하나씩 확인하는 반면, 이진 탐색은 중간값과 비교하여 탐색 범위를 절반으로 줄이는 분할 정복(Divide and Conquer) 전략을 사용합니다. 이 알고리즘은 코딩 테스트에서 자주 출제되며, 대용량 데이터 검색에 필수적인 기술입니다.

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

이진 탐색의 동작 원리는 다음과 같습니다. 먼저 정렬된 배열의 중간 인덱스를 계산합니다. 중간값이 찾고자 하는 목표값과 같다면 탐색을 종료하고 해당 인덱스를 반환합니다. 중간값이 목표값보다 크다면 배열의 왼쪽 절반에서 탐색을 계속하고, 작다면 오른쪽 절반에서 탐색합니다. 이 과정을 목표값을 찾거나 탐색 범위가 없어질 때까지 반복합니다.

예를 들어 [1, 3, 5, 7, 9, 11, 13, 15, 17, 19] 배열에서 7을 찾는다면:

• 1단계: 중간값 9와 비교 → 7 < 9이므로 왼쪽 절반 탐색
• 2단계: [1, 3, 5, 7]의 중간값 3과 비교 → 7 > 3이므로 오른쪽 절반 탐색
• 3단계: [5, 7]의 중간값 5와 비교 → 7 > 5이므로 오른쪽 절반 탐색
• 4단계: 7 발견, 인덱스 3 반환

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

시간 복잡도: 이진 탐색의 시간 복잡도는 O(log n)입니다. 매 단계마다 탐색 범위가 절반으로 줄어들기 때문에, n개의 요소를 가진 배열에서 최대 log₂n번의 비교만으로 결과를 찾을 수 있습니다. 예를 들어 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) {
      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, 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, left, mid - 1);
  } else {
    return binarySearchRecursive(arr, target, mid + 1, right);
  }
}

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

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, 5];
console.log(lowerBound(duplicates, 2)); // 1 (첫 번째 2의 위치)
console.log(upperBound(duplicates, 2)); // 4 (2 다음 값의 위치)

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

5.1 오버플로우 방지

중간 인덱스 계산 시 Math.floor((left + right) / 2) 대신 Math.floor(left + (right - left) / 2)를 사용하면 큰 수에서 발생할 수 있는 오버플로우를 방지할 수 있습니다.

5.2 비트 연산 활용

성능을 극대화하려면 비트 시프트 연산을 활용할 수 있습니다:

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

5.3 정렬 여부 검증

JavaScript로 이진 탐색 구현하기에서 가장 흔한 실수는 정렬되지 않은 배열에 이진 탐색을 적용하는 것입니다. 실무에서는 사전 검증 로직을 추가하는 것이 좋습니다:

function safeBinarySearch(arr, target) {
  // 배열이 정렬되어 있는지 확인 (개발 환경에서만)
  if (process.env.NODE_ENV === 'development') {
    const isSorted = arr.every((val, i) => i === 0 || arr[i - 1] <= val);
    if (!isSorted) {
      console.warn('Warning: Array is not sorted!');
    }
  }
  
  return binarySearch(arr, target);
}

6. 실전 활용 예제

6.1 숫자 배열에서 특정 범위 찾기

function findRange(arr, target) {
  const first = lowerBound(arr, target);
  const last = upperBound(arr, target) - 1;
  
  if (first <= last && arr[first] === target) {
    return [first, last];
  }
  return [-1, -1];
}

const nums = [5, 7, 7, 8, 8, 8, 10];
console.log(findRange(nums, 8)); // [3, 5]

6.2 회전 정렬 배열에서 검색

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

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

6.3 제곱근 구하기 (이진 탐색 응용)

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
console.log(sqrt(8));  // 2

7. 마무리 및 핵심 정리

JavaScript로 이진 탐색 구현하기를 마스터하면 효율적인 검색 알고리즘을 자유자재로 활용할 수 있습니다. 핵심 포인트를 정리하면:

• 필수 조건: 배열이 반드시 정렬되어 있어야 함
• 시간 복잡도: O(log n)으로 매우 효율적
• 구현 방식: 반복문(권장) 또는 재귀 중 선택
• 활용 범위: 단순 검색부터 복잡한 최적화 문제까지 광범위
• 주의사항: 중간 인덱스 계산 시 오버플로우 방지

이진 탐색은 코딩 테스트의 단골 주제이며, Lower Bound와 Upper Bound 같은 변형 기법까지 숙달하면 다양한 문제를 해결할 수 있습니다. 지금 바로 실전 문제에 적용해보세요!