이진 탐색을 사용할 수 있는 조건은 무엇인가요?

이진 탐색은 탐색 범위를 절반씩 줄여 O(log n)에 답을 찾는 기법입니다. 사용할 수 있는 핵심 조건은 데이터나 답의 후보 공간에 단조성(monotonicity)이 있어 '왼쪽/오른쪽 중 어느 쪽을 버릴지' 판단할 수 있어야 한다는 점입니다.

핵심 개념

• 가장 전형적인 조건은 배열이 정렬되어 있는 것입니다.
• 정렬 배열이 아니어도 조건을 만족하는 최소/최대 값처럼 true/false가 한 번만 바뀌는 문제에 사용할 수 있습니다.
• 각 단계에서 중간값을 검사하고 답이 있을 수 없는 절반을 버립니다.

동작 방식 또는 판단 기준

이 주제를 이해할 때는 다음 순서로 보면 실무 적용이 쉬워집니다.

1. 무엇을 해결하려는가: 성능, 표현력, 안정성, 접근성 중 어떤 문제를 줄이려는지 확인합니다.
2. 전제 조건은 무엇인가: 정렬 여부, 브라우저 지원, 네트워크 특성, 동시성 조건처럼 성립해야 하는 조건을 점검합니다.
3. 비용은 어디서 발생하는가: 시간 복잡도, 메모리, 캐시, 재시도, 렌더링 비용처럼 병목 지점을 나눠 봅니다.
4. 실패 시 어떤 문제가 생기는가: 잘못 적용했을 때의 버그나 운영 리스크를 함께 고려합니다.

실제 예시

function lowerBound(arr, target) {
  let lo = 0, hi = arr.length; // [lo, hi)
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid;
  }
  return lo; // target 이상이 처음 나오는 위치
}

Parametric search 예:
"x시간 안에 모든 작업을 끝낼 수 있는가?"
x가 커질수록 가능성이 단조롭게 증가하면 최소 x를 이진 탐색 가능

실무에서 주의할 점

• 정렬되지 않았거나 단조성이 없으면 이진 탐색은 잘못된 결과를 냅니다.
• lo, hi, mid 갱신 규칙이 일관되지 않으면 무한 루프나 off-by-one 버그가 발생합니다.
• 부동소수점 이진 탐색은 종료 조건과 오차 허용 범위를 명확히 해야 합니다.

실무 적용 가이드

• 반열린 구간 [lo, hi) 또는 닫힌 구간 [lo, hi] 중 하나를 정해 끝까지 유지합니다.
• '처음으로 조건을 만족하는 위치'와 '마지막으로 만족하는 위치'를 구분합니다.
• 정렬 비용 O(n log n)이 탐색 횟수 대비 정당한지도 함께 판단합니다.

함께 연결해서 보면 좋은 키워드

Binary Search, Lower Bound, Monotonicity, Parametric Search

정리

이진 탐색은 탐색 범위를 절반씩 줄여 O(log n)에 답을 찾는 기법입니다. 다만 개념 자체보다 중요한 것은 적용 조건과 한계를 함께 이해하는 것입니다. 작은 예제에서는 단순해 보여도 실제 서비스에서는 성능, 보안, 유지보수성, 접근성 요구사항이 함께 얽히므로, 문제의 성격을 먼저 파악한 뒤 적절한 도구로 선택하는 것이 좋습니다.