이진 탐색: 경계 조건, lower/upper bound, 결정 문제로 바꾸는 파라메트릭 서치

시리즈 안내

#09 | 📋 전체 목차 | 이전: #08 정렬 문제 · 다음: #10 BFS와 DFS

---

들어가며

이진 탐색은 정렬된 배열에서 O(log n)으로 값을 찾는 알고리즘입니다. 선형 탐색 O(n)보다 훨씬 빠릅니다.

---

사전 지식 (초보자를 위한 기초)

배열이란?

배열은 여러 개의 값을 순서대로 저장하는 자료구조입니다. 책장에 책을 순서대로 꽂아두는 것과 같습니다.

# 배열 예시
arr = [1, 3, 5, 7, 9, 11, 13, 15]
#      0  1  2  3  4   5   6   7  (인덱스 = 위치)
# 인덱스로 값 접근
print(arr[0])  # 1 (첫 번째 값)
print(arr[3])  # 7 (네 번째 값)

정렬된 배열이란?

정렬된 배열은 값이 작은 것부터 큰 순서로 나열된 배열입니다.

# 정렬된 배열
sorted_arr = [1, 3, 5, 7, 9]  # ✅ 작은 것 → 큰 것
# 정렬되지 않은 배열
unsorted_arr = [5, 1, 9, 3, 7]  # ❌ 순서가 뒤죽박죽

왜 정렬이 중요한가?

• 이진 탐색은 정렬된 배열에서만 작동합니다
• 정렬되지 않은 배열은 먼저 정렬해야 합니다

시간 복잡도란?

시간 복잡도는 알고리즘이 얼마나 빠른지 나타내는 지표입니다.

# O(n) - 선형 탐색 (느림)
# 배열의 모든 요소를 하나씩 확인
def linear_search(arr, target):
    for i in range(len(arr)):  # n번 반복
        if arr[i] == target:
            return i
    return -1
# 예시: 배열 크기가 1000개면 최악의 경우 1000번 확인
# O(log n) - 이진 탐색 (빠름)
# 배열을 절반씩 줄여가며 확인
# 예시: 배열 크기가 1000개면 최악의 경우 10번만 확인
# 1000 → 500 → 250 → 125 → 62 → 31 → 15 → 7 → 3 → 1

비교:

배열 크기	O(n) 선형 탐색	O(log n) 이진 탐색
10개	10번	4번
100개	100번	7번
1,000개	1,000번	10번
1,000,000개	1,000,000번	20번

이진 탐색이 훨씬 빠릅니다!

이진 탐색의 핵심 아이디어

“사전에서 단어 찾기”를 생각해보세요:

사전에서 "사과" 찾기:
1. 사전을 가운데 펼침 → "마" 나옴
2. "사"는 "마"보다 뒤에 있음 → 앞쪽 절반은 버림
3. 남은 절반의 가운데 펼침 → "자" 나옴
4. "사"는 "자"보다 앞에 있음 → 뒤쪽 절반은 버림
5. 남은 절반의 가운데 펼침 → "사" 찾음!
매번 절반씩 버리므로 빠르게 찾을 수 있습니다!

이진 탐색도 똑같은 원리입니다:

1. 배열의 가운데 값을 확인
2. 찾는 값이 가운데보다 작으면 → 왼쪽 절반만 탐색
3. 찾는 값이 가운데보다 크면 → 오른쪽 절반만 탐색
4. 반복하면 빠르게 찾을 수 있음

사전 비유가 성립하는 조건이 곧 이진 탐색의 전제 조건입니다. 사전이 가나다순으로 정렬되어 있기 때문에 “마”를 보고 “사”가 뒤에 있다고 확신할 수 있고, 그래서 앞쪽 절반을 한 번도 보지 않고 버릴 수 있습니다. 정렬되어 있지 않다면 가운데 값이 무엇이든 찾는 값이 어느 쪽에 있는지 알 수 없어 절반을 버릴 근거가 사라집니다. 더 일반적으로 말하면 이진 탐색에 필요한 것은 “정렬” 자체가 아니라 단조성입니다. 어떤 위치를 기준으로 왼쪽은 모두 조건을 만족하지 않고 오른쪽은 모두 만족하는 구조라면, 배열이 아니어도 이진 탐색을 쓸 수 있습니다. 이 관점이 뒤에서 다룰 파라메트릭 서치의 출발점입니다.

한 가지 비용도 알아 둬야 합니다. 정렬되지 않은 데이터에서 값 하나를 찾으려고 O(n log n)을 들여 정렬하면 O(n) 선형 탐색보다 오히려 느립니다. 이진 탐색이 이득인 것은 한 번 정렬해 두고 여러 번 검색하는 경우입니다. 검색이 k번이라면 정렬 비용 O(n log n)에 검색 k × O(log n)이 더해지고, 선형 탐색의 k × O(n)보다 작아지는 지점부터 의미가 생깁니다.

---

이진 탐색 기본

알고리즘

[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]에서 7 찾기
1. 중간값 확인: arr[4] = 9 > 7 → 왼쪽 절반
2. 중간값 확인: arr[1] = 3 < 7 → 오른쪽 절반
3. 중간값 확인: arr[2] = 5 < 7 → 오른쪽 절반
4. 중간값 확인: arr[3] = 7 = 7 → 찾음!

Python 구현

이진 탐색은 정렬된 배열을 절반씩 잘라 탐색 범위를 줄입니다. 사전에서 단어를 찾을 때 가운데를 펼쳐 보며, 찾는 글자가 앞쪽인지 뒤쪽인지로 절반을 버리는 것과 같은 방식입니다.

def binary_search(arr, target):
    # 탐색 범위: [left, right]
    left, right = 0, len(arr) - 1
    
    # left가 right를 넘어가면 못 찾은 것
    while left <= right:
        # 중간 인덱스 계산
        mid = (left + right) // 2
        # 주의: (left + right) / 2는 오버플로우 가능 (C/C++)
        # Python은 정수 오버플로우 없음
        # 더 안전한 방법: mid = left + (right - left) // 2
        
        if arr[mid] == target:
            # 찾았음!
            return mid
        elif arr[mid] < target:
            # 중간값이 target보다 작음
            # target은 오른쪽 절반에 있음
            left = mid + 1  # 왼쪽 절반 버림
        else:
            # 중간값이 target보다 큼
            # target은 왼쪽 절반에 있음
            right = mid - 1  # 오른쪽 절반 버림
    
    # 못 찾음
    return -1
# 테스트
arr = [1, 3, 5, 7, 9, 11, 13, 15]
print(binary_search(arr, 7))   # 3 (인덱스 3에 7이 있음)
print(binary_search(arr, 10))  # -1 (10은 배열에 없음)
# 탐색 과정 (target=7):
# arr = [1, 3, 5, 7, 9, 11, 13, 15]
#        0  1  2  3  4   5   6   7  (인덱스)
#
# 1단계: left=0, right=7
#   mid = (0+7)//2 = 3
#   arr[3] = 7 == 7 → 찾음!
#   return 3
#
# 탐색 과정 (target=11):
# 1단계: left=0, right=7
#   mid = 3, arr[3] = 7 < 11
#   left = 4 (오른쪽 절반으로)
#
# 2단계: left=4, right=7
#   mid = (4+7)//2 = 5
#   arr[5] = 11 == 11 → 찾음!
#   return 5
#
# 시간복잡도: O(log n)
# 매번 탐색 범위가 절반으로 줄어듦
# n=1000 → 최대 10번 비교
# n=1000000 → 최대 20번 비교

이 구현에서 경계 조건 세 가지는 한 세트로 맞물려 있습니다. 탐색 범위를 양 끝을 포함하는 닫힌 구간 [left, right]로 잡았기 때문에 right = len(arr) - 1로 시작하고, left == right일 때도 원소가 하나 남아 있으므로 조건이 left <= right이며, mid는 이미 확인했으니 다음 범위에서 빼기 위해 mid + 1, mid - 1로 좁힙니다. 이 중 하나만 바꾸면 버그가 됩니다. 예를 들어 조건을 left < right로 바꾸면 원소가 하나 남았을 때 확인하지 않고 끝나서, 배열 [5]에서 5를 못 찾습니다. right = mid - 1 대신 right = mid로 쓰면 left == right == mid인 상태에서 범위가 줄지 않아 무한 루프에 빠집니다.

제가 코딩 테스트 연습을 하며 가장 자주 낸 버그가 이 무한 루프였고, 원인은 늘 다른 코드의 경계 규칙을 반쯤 섞어 쓴 것이었습니다. 그래서 지금은 “닫힌 구간이면 <=와 ±1, 반열린 구간이면 <와 right = mid”를 한 쌍으로 외워 두고 섞지 않습니다. 확신이 서지 않으면 원소 0개, 1개, 2개짜리 배열과 찾는 값이 맨 앞·맨 뒤·없는 경우를 직접 넣어 보면 경계 버그는 거의 다 드러납니다. 선형 탐색 vs 이진 탐색:

# 선형 탐색: O(n)
def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1
# 최악의 경우: 모든 요소 확인 (n번)
# 이진 탐색: O(log n)
# 최악의 경우: log₂(n)번만 확인
# 
# 성능 비교 (n=1000000):
# 선형: 1000000번 비교 (최악)
# 이진: 20번 비교 (최악)
# → 비교 횟수 기준 50000배 적음

비교 횟수 차이가 그대로 실행 시간 차이가 되지는 않습니다. 원소가 수십 개 정도로 적으면 선형 탐색이 CPU 캐시와 분기 예측에 유리해서 이진 탐색보다 빠른 경우도 흔합니다. 이진 탐색은 메모리를 여기저기 건너뛰며 읽기 때문입니다. 반대로 데이터가 커질수록 로그의 위력이 압도적이 되어, 코딩 테스트에서 “n이 10만 이상이고 검색이 n번”이면 선형 탐색은 거의 확실히 시간 초과입니다.

재귀 구현

def binary_search_recursive(arr, target, left, right):
    if left > right:
        return -1
    
    mid = (left + right) // 2
    
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        return binary_search_recursive(arr, target, left, mid - 1)
# 사용
arr = [1, 3, 5, 7, 9]
print(binary_search_recursive(arr, 7, 0, len(arr) - 1))  # 3

재귀 버전은 반복 버전과 논리가 같고, 탐색 범위를 매개변수로 넘긴다는 점만 다릅니다. 재귀 깊이가 log₂(n)이라 100만 개여도 20단계 정도라서 Python의 기본 재귀 한도(1000)에 걸릴 일은 없습니다. 그래도 실무와 코딩 테스트에서는 반복 버전을 더 많이 씁니다. 함수 호출 비용이 없고, 호출자가 0, len(arr) - 1을 직접 넘겨야 하는 불편함도 없기 때문입니다. 재귀 버전을 쓴다면 left=0, right=None 기본값을 두고 함수 안에서 right를 채우는 식으로 호출을 단순하게 만드는 편이 좋습니다.

앞의 기본 이진 탐색에는 알아 둬야 할 한계가 하나 있습니다. 같은 값이 여러 개 있으면 그중 아무거나 하나의 인덱스를 돌려줍니다. [1, 2, 2, 2, 3]에서 2를 찾으면 가운데 인덱스 2가 먼저 걸려 반환되는데, “첫 번째 2”나 “마지막 2”가 필요하다면 이 함수로는 알 수 없습니다. 이 문제를 푸는 것이 다음 절의 Lower Bound와 Upper Bound입니다.

---

Lower Bound & Upper Bound

Lower Bound

x 이상인 첫 번째 위치를 찾습니다:

def lower_bound(arr, x):
    # 탐색 범위: [left, right)
    # right = len(arr)로 설정 (배열 끝 다음)
    left, right = 0, len(arr)
    
    # left == right가 되면 종료
    while left < right:
        mid = (left + right) // 2
        
        # arr[mid] < x: mid는 답이 될 수 없음
        if arr[mid] < x:
            # x보다 작으면 오른쪽으로
            left = mid + 1
        else:
            # arr[mid] >= x: mid가 답일 수 있음
            # x 이상이면 왼쪽으로 (더 작은 인덱스 찾기)
            right = mid
    
    # left가 x 이상인 첫 위치
    return left
# 테스트
arr = [1, 2, 2, 2, 3, 4, 5]
#      0  1  2  3  4  5  6  (인덱스)
print(lower_bound(arr, 2))  # 1 (첫 번째 2의 위치)
# 2 이상인 첫 위치 = 인덱스 1
print(lower_bound(arr, 3))  # 4 (3의 위치)
# 3 이상인 첫 위치 = 인덱스 4
print(lower_bound(arr, 0))  # 0 (배열 시작)
# 0 이상인 첫 위치 = 인덱스 0
print(lower_bound(arr, 10))  # 7 (배열 끝)
# 10 이상인 값이 없음 → len(arr) 반환
# 탐색 과정 (x=2):
# arr = [1, 2, 2, 2, 3, 4, 5]
#
# 1단계: left=0, right=7
#   mid = 3, arr[3] = 2 >= 2
#   right = 3 (mid가 답일 수 있음)
#
# 2단계: left=0, right=3
#   mid = 1, arr[1] = 2 >= 2
#   right = 1
#
# 3단계: left=0, right=1
#   mid = 0, arr[0] = 1 < 2
#   left = 1
#
# 4단계: left=1, right=1
#   종료 → return 1

Lower Bound가 기본 이진 탐색과 다른 점은 찾았다고 바로 멈추지 않는다는 것입니다. arr[mid] >= x인 경우 mid가 답일 수 있지만 더 왼쪽에 답이 있을 수도 있으므로, mid를 범위에 남긴 채(right = mid) 왼쪽을 계속 찾습니다. 그래서 범위를 반열린 구간 [left, right)로 잡고, left == right가 되어 후보가 하나로 좁혀질 때 끝냅니다. 반환값은 항상 0부터 len(arr) 사이의 값이고, len(arr)이 나오면 “x 이상인 값이 없다”는 뜻입니다.

이 반환값을 바로 인덱스로 쓰는 것이 흔한 실수입니다. lower_bound(arr, 10)은 7을 반환하는데, arr[7]에 접근하면 IndexError: list index out of range가 납니다. 또 “x가 배열에 있는가”를 확인하려면 i < len(arr) and arr[i] == x까지 검사해야 합니다. Lower Bound는 “있다면 여기, 없다면 여기에 넣으면 된다”는 위치를 줄 뿐, 존재 여부를 알려 주지는 않습니다. Lower Bound 활용:

# 1. 중복된 값의 첫 위치 찾기
arr = [1, 2, 2, 2, 3, 4, 5]
first_2 = lower_bound(arr, 2)  # 1
# 2. 삽입 위치 찾기 (정렬 유지)
arr = [1, 3, 5, 7, 9]
pos = lower_bound(arr, 6)  # 3
arr.insert(pos, 6)  # [1, 3, 5, 6, 7, 9]
# 3. 범위 쿼리 (x 이상인 개수)
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
count_gte_5 = len(arr) - lower_bound(arr, 5)  # 5
# 5 이상: [5, 6, 7, 8, 9] → 5개

Upper Bound

x 초과인 첫 번째 위치를 찾습니다:

def upper_bound(arr, x):
    # 탐색 범위: [left, right)
    left, right = 0, len(arr)
    
    while left < right:
        mid = (left + right) // 2
        
        # arr[mid] <= x: mid는 답이 될 수 없음
        if arr[mid] <= x:
            # x 이하면 오른쪽으로
            left = mid + 1
        else:
            # arr[mid] > x: mid가 답일 수 있음
            # x 초과면 왼쪽으로 (더 작은 인덱스 찾기)
            right = mid
    
    # left가 x 초과인 첫 위치
    return left
# 테스트
arr = [1, 2, 2, 2, 3, 4, 5]
#      0  1  2  3  4  5  6  (인덱스)
print(upper_bound(arr, 2))  # 4 (2 다음 위치)
# 2 초과인 첫 위치 = 인덱스 4 (값 3)
print(upper_bound(arr, 3))  # 5 (3 다음 위치)
# 3 초과인 첫 위치 = 인덱스 5 (값 4)
print(upper_bound(arr, 5))  # 7 (배열 끝)
# 5 초과인 값이 없음 → len(arr) 반환
# Lower Bound vs Upper Bound:
# arr = [1, 2, 2, 2, 3, 4, 5]
#        0  1  2  3  4  5  6
#
# x=2:
# lower_bound(arr, 2) = 1  (2 이상인 첫 위치)
# upper_bound(arr, 2) = 4  (2 초과인 첫 위치)
#
# 차이: upper_bound - lower_bound = 중복 개수
# 4 - 1 = 3 (2가 3개)

Upper Bound 활용:

# 1. 중복된 값의 마지막 다음 위치
arr = [1, 2, 2, 2, 3, 4, 5]
last_2_next = upper_bound(arr, 2)  # 4
# 2의 마지막 인덱스 = last_2_next - 1 = 3
# 2. 중복 개수 세기
def count_occurrences(arr, x):
    return upper_bound(arr, x) - lower_bound(arr, x)
arr = [1, 2, 2, 2, 3, 4, 5]
print(count_occurrences(arr, 2))  # 3
# upper_bound(2) - lower_bound(2) = 4 - 1 = 3
# 3. 범위 쿼리 (x 이하인 개수)
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
count_lte_5 = upper_bound(arr, 5)  # 5
# 5 이하: [1, 2, 3, 4, 5] → 5개
# 4. 삽입 위치 (중복 허용, 뒤에 삽입)
arr = [1, 2, 2, 2, 3]
pos = upper_bound(arr, 2)  # 4
arr.insert(pos, 2)  # [1, 2, 2, 2, 2, 3]

C++ STL 함수:

#include <algorithm>
#include <vector>
std::vector<int> arr = {1, 2, 2, 2, 3, 4, 5};
// Lower Bound: x 이상인 첫 위치
auto it1 = std::lower_bound(arr.begin(), arr.end(), 2);
// it1 = arr.begin() + 1
// Upper Bound: x 초과인 첫 위치
auto it2 = std::upper_bound(arr.begin(), arr.end(), 2);
// it2 = arr.begin() + 4
// 개수 세기
int count = it2 - it1;  // 3

두 함수의 코드는 비교 연산자 하나(< 대 <=)만 다릅니다. Lower Bound는 “x보다 작은 것”을 왼쪽으로 몰아내고, Upper Bound는 “x 이하인 것”을 몰아내므로, 두 위치 사이가 정확히 x와 같은 원소들의 구간이 됩니다. C++에서는 std::equal_range가 두 값을 한 번에 돌려주고, Python의 bisect_left/bisect_right가 각각 Lower/Upper Bound에 해당합니다.

C++ 쪽에서 주의할 점은 std::lower_bound를 std::set이나 std::map에 쓰는 경우입니다. std::lower_bound(s.begin(), s.end(), x)는 컴파일도 되고 결과도 맞지만, 트리 컨테이너의 반복자는 임의 접근이 안 되어 O(n)으로 동작합니다. 멤버 함수 s.lower_bound(x)를 써야 O(log n)입니다. 코딩 테스트에서 정답인데 시간 초과가 나는 대표적인 원인입니다.

개수 세기

def count_occurrences(arr, x):
    """
    정렬된 배열에서 x의 개수 (O(log n))
    """
    return upper_bound(arr, x) - lower_bound(arr, x)
# 테스트
arr = [1, 2, 2, 2, 3, 4, 5]
print(count_occurrences(arr, 2))  # 3

---

파라메트릭 서치

개념

최적화 문제 → 결정 문제로 변환:

"최소 몇 개?" → "k개로 가능한가?" (이진 탐색)

파라메트릭 서치의 핵심은 답의 범위를 배열처럼 보는 것입니다. 나무 자르기 문제에서 절단 높이 h는 0부터 가장 높은 나무까지의 정수 중 하나이고, “높이 h로 자르면 target 이상 얻는가?”라는 질문의 답은 h가 커질수록 참에서 거짓으로 한 번만 바뀝니다. 낮게 자를수록 많이 얻으니까요. 이 단조성이 있으면 답의 범위를 [참, 참, 참, 거짓, 거짓] 같은 정렬된 배열로 볼 수 있고, “마지막 참”의 위치를 이진 탐색으로 찾으면 됩니다. “최대 높이를 직접 계산하는 공식”을 떠올리기는 어렵지만, “이 높이로 되는가”를 확인하는 함수는 한 줄로 쓸 수 있다는 것이 이 기법의 힘입니다.

문제를 보고 파라메트릭 서치를 떠올리는 신호는 “~의 최댓값/최솟값을 구하라”는 요구와 함께 답의 범위가 매우 큰 경우(10⁹ 등)입니다. 모든 후보를 하나씩 확인하면 시간 초과지만, 이진 탐색이면 30번 정도의 판정으로 끝납니다.

예제: 나무 자르기

def cut_trees(trees, h):
    """
    높이 h로 잘랐을 때 얻는 나무 길이
    """
    return sum(max(0, tree - h) for tree in trees)
def find_max_height(trees, target):
    """
    target 길이 이상을 얻을 수 있는 최대 높이
    """
    left, right = 0, max(trees)
    result = 0
    
    while left <= right:
        mid = (left + right) // 2
        
        if cut_trees(trees, mid) >= target:
            result = mid  # 가능 → 더 높게
            left = mid + 1
        else:
            right = mid - 1  # 불가능 → 더 낮게
    
    return result
# 테스트
trees = [20, 15, 10, 17]
target = 7
print(find_max_height(trees, target))  # 15
# 높이 15로 자르면: 5 + 0 + 0 + 2 = 7

이 코드는 앞의 기본 이진 탐색과 같은 닫힌 구간 방식이지만, 조건을 만족하는 mid를 result에 기록해 두고 더 좋은 답을 찾아 계속 진행한다는 점이 다릅니다. 가능하면 더 높게(left = mid + 1), 불가능하면 더 낮게(right = mid - 1) 움직이고, 루프가 끝났을 때 result에 남은 값이 “가능한 최대 높이”입니다. 확인 과정을 따라가 보면 h=15에서 정확히 7을 얻어 가능하고, h=16에서는 4+1=5라 불가능하므로 답은 15입니다.

실제 백준 2805번을 풀 때는 두 가지 함정이 있습니다. 첫째, 나무가 최대 100만 그루이고 판정을 약 30번 하므로 cut_trees가 총 3천만 번의 연산을 합니다. Python의 제너레이터 합계로는 시간 제한에 걸리기 쉬워, 반복문을 최소화하거나 PyPy로 제출해야 하는 경우가 많습니다. 둘째, C++로 옮기면 잘린 길이의 합이 최대 10⁶ × 10⁹ = 10¹⁵로 int 범위(약 21억)를 훨씬 넘으므로 합계 변수를 long long으로 둬야 합니다. 합이 오버플로하면 음수가 되어 “불가능”으로 잘못 판정되고, 예제는 통과하는데 제출하면 틀리는 가장 흔한 원인이 됩니다. 1654번 랜선 자르기도 같은 구조인데, 길이가 1 이상이어야 하므로 left = 1로 시작해야 0으로 나누는 오류를 피할 수 있습니다.

---

bisect 모듈과 mid 계산에서 챙길 것

bisect 모듈 활용

import bisect
arr = [1, 2, 3, 5, 6, 7]
idx = bisect.bisect_left(arr, 4)   # Lower Bound
print(idx)  # 3
bisect.insort(arr, 4)  # 정렬 유지하며 삽입
print(arr)  # [1, 2, 3, 4, 5, 6, 7]

bisect 모듈은 C로 구현되어 직접 작성한 이진 탐색보다 빠르고 경계 버그 걱정도 없으므로, 코딩 테스트에서 Lower/Upper Bound가 필요하면 먼저 bisect_left/bisect_right를 떠올리세요. Python 3.10부터는 key 인자도 받아서, 튜플 리스트의 특정 필드를 기준으로 찾을 수 있습니다. 단, insort는 위치를 O(log n)에 찾더라도 리스트 삽입 자체가 O(n)입니다. 삽입이 수십만 번 반복되면 전체가 O(n²)이 되므로, 그런 경우에는 힙(heapq)이나 균형 트리 기반 자료구조가 더 맞습니다.

mid 계산 오버플로

# ❌ 오버플로우 주의 (C++)
# mid = (left + right) / 2;  // left + right 오버플로우!
# ✅ 안전한 방법
# mid = left + (right - left) / 2;
# Python은 오버플로우 걱정 없음
mid = (left + right) // 2

이 오버플로 버그는 이론상의 이야기가 아닙니다. Java 표준 라이브러리의 Arrays.binarySearch에도 (low + high) / 2가 거의 10년간 들어 있다가, 원소가 2³⁰개를 넘는 배열에서 문제가 된다는 사실이 2006년에 알려져 수정된 유명한 사례가 있습니다. 배열 인덱스로는 그렇게 큰 값을 만날 일이 드물지만, 파라메트릭 서치에서는 답의 범위가 [0, 2×10⁹]처럼 int 한계에 가까운 경우가 흔해 실제로 자주 터집니다. C++에서는 left + (right - left) / 2를 쓰거나, 범위 자체를 long long으로 잡으면 안전합니다. 또 음수 범위를 탐색할 때는 C++의 /가 0 쪽으로 버림하고 Python의 //는 음의 무한대 쪽으로 버림하므로, 같은 코드라도 두 언어에서 mid가 달라질 수 있다는 점도 알아 두세요.

---

추천 문제와 경계 조건 함정

이진 탐색 코드가 틀리는 이유는 거의 항상 경계입니다. lo = mid로 구간을 줄이면서 mid = (lo + hi) // 2를 쓰면, hi = lo + 1이 된 순간 mid가 계속 lo에 머물러 무한 루프가 됩니다. 구간을 [lo, hi)처럼 반열림으로 정하든 닫힌 구간으로 정하든 하나로 통일하고, 루프가 끝났을 때 lo가 무엇을 가리키는지를 먼저 적어 두면 이런 실수가 줄어듭니다.

파라메트릭 서치 문제(나무 자르기, 랜선 자르기, 입국심사)에서는 답의 범위를 잘못 잡는 경우가 많습니다. 랜선 자르기는 길이가 0이 될 수 없으므로 하한을 1로 두어야 0으로 나누는 오류를 피할 수 있고, 입국심사는 상한이 “가장 느린 심사관 시간 × 사람 수”만큼 커지므로 C++이나 Java에서는 64비트 정수를 써야 합니다.

백준:

• 1920번: 수 찾기
• 2805번: 나무 자르기
• 1654번: 랜선 자르기

프로그래머스:

• 입국심사

LeetCode:

• 704. Binary Search
• 35. Search Insert Position

---

같이 보면 좋은 글

• 기초 정렬 알고리즘
• 알고리즘 시리즈 전체 목차
• 배열과 리스트
• 스택과 큐
• BFS와 DFS
• 정렬 문제 풀이

---

자주 묻는 질문 (FAQ)

Q. C++에서 mid = (left + right) / 2를 쓰면 왜 위험한가요?

A. left와 right가 모두 int 범위의 큰 값이면 두 값을 더하는 순간 오버플로가 나서 mid가 음수나 엉뚱한 값이 됩니다. mid = left + (right - left) / 2처럼 차이를 먼저 구하면 같은 값을 오버플로 없이 얻을 수 있습니다. Python은 정수 크기에 제한이 없어 (left + right) // 2를 그대로 써도 되지만, 파라메트릭 서치처럼 탐색 범위가 큰 문제를 C++로 옮길 때는 꼭 신경 써야 합니다.

---