이진 탐색

정렬된 배열 [2, 5, 8, 12, 16]에서 16을 찾아봅니다. 왼쪽 끝 lo와 오른쪽 끝 hi를 잡고, 가운데 mid를 확인하며 범위를 좁힙니다.

원소 5개를 3번 만에 찾았습니다. 앞에서부터 하나씩 봤다면 5번이 걸립니다. 차이가 작아 보이지만 원소가 100만 개면 100만 번 대 20번입니다.

여기서 눈여겨볼 것은 버리는 폭입니다. 1단계에서 arr[2] = 8이 목표보다 작다는 사실 하나로 인덱스 0, 1, 2 세 칸을 한꺼번에 지웠습니다. 배열이 정렬되어 있기 때문에 "8보다 앞은 전부 8 이하"라고 말할 수 있고, 이 근거가 없으면 절반 버리기는 성립하지 않습니다.

1. 찾을 범위의 양 끝을 잡습니다. 배열 탐색이면 0과 length - 1입니다.

let lo = 0, hi = arr.length - 1;

2. 범위가 남아 있는 동안 반복합니다. 양 끝이 교차하면 후보가 없다는 뜻입니다.

while (lo <= hi) { /* ... */ }

3. 가운데를 계산해 확인합니다.

const mid = (lo + hi) >> 1; // Math.floor((lo + hi) / 2)와 같음
if (arr[mid] === target) return mid;

4. 찾는 값이 아니면 절반을 버립니다. 확인한 mid는 다시 볼 필요가 없으므로 ±1을 붙입니다.

if (arr[mid] < target) lo = mid + 1; // 오른쪽만 남김
else hi = mid - 1;                   // 왼쪽만 남김

전체 코드 — 정렬된 배열에서 값의 위치 찾기:

function binarySearch(arr: number[], target: number): number {
  let lo = 0, hi = arr.length - 1;      // 1단계
  while (lo <= hi) {                    // 2단계
    const mid = (lo + hi) >> 1;         // 3단계
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) lo = mid + 1; // 4단계
    else hi = mid - 1;
  }
  return -1;                            // 끝까지 못 찾음
}

• 입력이 이미 정렬되어 있거나, 정렬해도 답이 변하지 않으면 일단 의심합니다. 정렬이 O(N log N)이라 붙여도 손해가 없습니다.
• "값이 있는지", "몇 번째인지", "몇 개인지"를 여러 번 물어보면 매 질문마다 O(log N)으로 답하는 이 유형입니다.
• "최댓값의 최솟값", "최소 시간", "가능한 최대 크기" 처럼 답 자체를 구하기는 어렵지만 "이 값이면 되는가"는 쉽게 판정할 수 있으면 파라메트릭 서치입니다.
• 제약이 N ≤ 100,000인데 답의 범위가 10억 단위라면, 답의 범위를 탐색하라는 신호입니다.

파라메트릭 서치 — 한국 코테 상급 단골은 배열 탐색이 아니라 "답을 이진 탐색"하는 이 형태입니다.

"속도 v로 하면 시간 내에 될까?" — v가 커질수록 항상 유리(단조)하다면, 가능/불가능의 경계값을 이진 탐색으로 찾을 수 있다.

// 뼈대: check(mid)가 "mid로 가능한가?"를 O(N)에 판정
function solve(): number {
  let lo = 1, hi = 1e12; // 답의 범위
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (check(mid)) hi = mid;      // 가능 → 더 작은 답 시도 (최솟값 찾기)
    else lo = mid + 1;             // 불가능 → 키워야 함
  }
  return lo; // 가능해지는 최초 지점
}

문제를 "X를 구하라"에서 "X = mid가 가능한가?"라는 예/아니오 질문으로 뒤집는 것이 전부입니다. 가능 여부가 mid에 대해 단조인지 반드시 먼저 확인하세요.

경계 변형 (lower/upper bound) — 중복이 있는 배열에서 위치나 개수를 물을 때 씁니다.

// lowerBound: target 이상이 처음 나오는 인덱스
function lowerBound(arr: number[], target: number): number {
  let lo = 0, hi = arr.length; // hi는 배열 밖까지
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

"target의 개수" = upperBound - lowerBound입니다. upperBound는 위 코드에서 비교를 arr[mid] <= target으로 바꾸면 됩니다.

• while (lo <= hi) vs while (lo < hi), hi = mid vs hi = mid - 1을 섞어 씀 — 한 세트를 정해 통째로 외우세요(위 두 뼈대처럼). 섞이면 무한 루프나 한 칸 오차가 납니다.

while (lo < hi) {
  const mid = (lo + hi) >> 1;
  if (check(mid)) hi = mid;
  else lo = mid;        // 잘못 — lo가 그대로일 수 있어 무한 루프
}

while (lo < hi) {
  const mid = (lo + hi) >> 1;
  if (check(mid)) hi = mid;
  else lo = mid + 1;    // 고침 — 범위가 반드시 줄어듦
}

• 파라메트릭에서 답 범위(lo, hi 초기값)를 좁게 잡아 정답을 범위 밖으로 놓칩니다. 넉넉하게 잡아도 로그라서 비용이 거의 없습니다.
• 단조성 확인 없이 이진 탐색 적용 — "가능↔불가능이 한 번만 바뀐다"가 성립해야 합니다.
• 큰 수 곱셈에서 정밀도: JS number는 2^53까지 정확하며, 그 이상은 BigInt를 씁니다.

• 왜 O(log N)인가: 매 단계 후보가 절반이 되므로, N이 1이 될 때까지의 횟수는 N을 2로 몇 번 나눌 수 있는지, 즉 log₂N입니다. 10억은 약 30번, 10^18도 60번입니다. 파라메트릭에서 check가 O(N)이면 전체는 O(N log(답의 범위))가 됩니다.
• (lo + hi) >> 1의 함정: JavaScript의 비트 연산은 피연산자를 32비트 정수로 바꿉니다. lo + hi가 2^31(약 21억)을 넘으면 값이 음수로 뒤집혀 틀립니다. 배열 인덱스에는 안전하지만, 답의 범위가 큰 파라메트릭 서치에서는 Math.floor((lo + hi) / 2)를 쓰세요. 위 두 뼈대가 서로 다른 방식인 이유가 이것입니다.
• 단조성을 만드는 전처리: 원래 단조가 아니어도 정렬·누적합·"이상/이하" 형태로 문제를 바꾸면 단조가 되는 경우가 많습니다. "K개 이하로 자를 수 있는가"처럼 조건을 부등호로 다시 쓰는 연습이 파라메트릭의 핵심입니다.
• 회전 배열 탐색: 정렬된 배열을 어느 지점에서 잘라 앞뒤를 바꾼 배열에서도 이진 탐색이 됩니다. mid를 기준으로 왼쪽 절반과 오른쪽 절반 중 정렬이 유지된 쪽을 판별하고, 목표가 그 구간 안에 있는지로 방향을 정합니다.
• 실수(부동소수점) 이진 탐색: 답이 정수가 아니면 lo < hi 대신 100회 정도 반복하거나 hi - lo > 1e-9를 종료 조건으로 씁니다. 정수 탐색과 달리 ±1 보정이 없습니다.

시각화로 "절반 버리기"의 리듬을 본 뒤, 기본 탐색 → lower/upper bound → 회전 배열 → 파라메트릭 서치 순으로. 파라메트릭까지 잡으면 이 유형은 졸업입니다.