이분 탐색, 무한 루프 없이 정확하게 구현하는 법

이분 탐색은 개념은 쉬운데 경계 조건에서 늘 미끄러집니다. 무한 루프와 off-by-one을 피하는 안정적인 틀을 익혀둡시다.

핵심 아이디어

정렬된 배열에서 가운데를 보고, 찾는 값이 그보다 크면 오른쪽, 작으면 왼쪽 절반만 다시 봅니다. 매번 범위가 절반이 되니 O(log n) 입니다.

기본 형태(값 찾기)

function binarySearch(arr, target) {
  let lo = 0, hi = arr.length - 1;
  while (lo <= hi) {                 // 닫힌 구간 [lo, hi]
    const mid = lo + ((hi - lo) >> 1); // 오버플로 방지
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1; // 못 찾음
}

세 가지 실수 포인트:

1. mid 계산: (lo + hi) / 2는 큰 수에서 오버플로 위험. lo + (hi - lo) / 2가 안전합니다(JS는 정수 오버플로가 없지만 습관으로).
2. 종료 조건: 닫힌 구간이면 lo <= hi. 등호를 빠뜨리면 마지막 한 칸을 놓칩니다.
3. 갱신: 반드시 mid + 1, mid - 1로 범위를 줄여야 무한 루프가 안 납니다.

lower bound: target 이상이 처음 나오는 위치

코딩테스트에서 더 자주 쓰이는 패턴입니다. "값 ≥ target인 첫 인덱스"를 찾습니다.

function lowerBound(arr, target) {
  let lo = 0, hi = arr.length; // 반열린 구간 [lo, hi)
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid;             // mid도 후보로 남김
  }
  return lo; // 삽입 위치이기도 함
}

반열린 구간(hi = length, lo < hi, hi = mid)을 쓰는 게 핵심입니다. 이 틀은 중복 값의 첫 위치나 삽입 위치를 깔끔히 줍니다.

"정답을 이분 탐색"하는 응용

"조건을 만족하는 최소 X"류 문제는 값 자체를 이분 탐색합니다.

가능한 답의 범위 [lo, hi]에서
mid가 조건을 만족? → hi = mid (더 작게 시도)
아니면 → lo = mid + 1

마무리 체크리스트

• 닫힌 구간엔 lo <= hi, 반열린엔 lo < hi
• mid는 lo + (hi-lo)/2
• 범위를 매번 줄였는지 확인(무한 루프 방지)
• 첫 위치/삽입 위치는 lower bound 틀로

두 가지 틀(값 찾기, lower bound)을 손에 익히면 대부분의 이분 탐색 문제를 실수 없이 풉니다.