[알고리즘 코어 파헤치기] 이분 탐색(Binary Search) 완벽 해부 - O(log N)의 마법과 파라메트릭 서치

학습 철학 회고
단순히 배열에서 숫자를 빨리 찾는 기법으로만 이분 탐색을 외우면, 정작 코딩 테스트의 꽃인 '파라메트릭 서치(Parametric Search)' 응용 문제를 풀지 못합니다. 탐색 공간을 반으로 접어 나간다는 본질적 철학과, left와 right 포인터가 교차하는 그 아슬아슬한 경계값을 어떻게 통제할 것인지 뼈대를 세웁니다.

📌 개념 요약: 이분 탐색이란 무엇인가?

1억 개의 데이터가 있을 때, 앞에서부터 하나씩 찾으면 최대 1억 번($O(N)$)이 걸리지만, "업 앤 다운" 게임처럼 중간값을 찔러보고 탐색 범위를 절반씩 날려버리면 단 27번($O(\log N)$) 만에 답을 찾아내는 극한의 최적화 알고리즘입니다.

• 절대 전제 조건: 탐색하려는 데이터는 반드시 정렬(Sorted)되어 있어야 합니다.
• 파라메트릭 서치(Parametric Search): "원하는 값을 찾아라"라는 문제를 "이 조건을 만족하는 가장 큰(혹은 작은) 값은 무엇인가?"라는 결정 문제(Yes/No)로 뒤집어서 푸는 고급 응용 기법입니다.

💡 동작 원리: 공간의 분할과 포인터 이동

이분 탐색의 핵심은 3개의 포인터(left, right, mid)를 관리하는 것입니다.
1. mid = (left + right) // 2로 중간 지점을 잡습니다.
2. 타겟이 mid보다 크다면, 정답은 무조건 오른쪽에 있으므로 left = mid + 1로 당겨옵니다.
3. 타겟이 mid보다 작다면, 정답은 무조건 왼쪽에 있으므로 right = mid - 1로 줄입니다.

💻 추상화된 템플릿 코드

가장 헷갈리는 '경계값 포함 여부(+1, -1)'를 명확하게 통제하는 순수 템플릿입니다. 특정 값을 찾는 기본형을 넘어, 조건을 만족하는 최댓값을 찾는 '파라메트릭 서치' 뼈대를 소개합니다.

def binary_search_parametric_template(arr, target_condition):
    """
    :param arr: 반드시 오름차순 정렬된 1차원 탐색 공간 (또는 가능한 값의 범위)
    :param target_condition: 결정 함수(Yes/No)에서 통과해야 할 목표치
    """
    left = 0
    right = len(arr) - 1 # 범위를 탐색할 땐 max(arr) 등으로 설정 가능
    
    # 1. 정답을 기록할 변수
    best_answer = -1 
    
    # 2. left와 right가 교차하기 전까지 무한 반복
    while left <= right:
        mid = (left + right) // 2
        
        # 3. [핵심 로직] 현재 mid 값이 우리가 원하는 조건을 만족하는가? (Yes/No 결정 함수)
        if check_condition(arr[mid]) >= target_condition:
            best_answer = arr[mid] # 일단 조건을 만족하므로 정답 후보에 기록
            left = mid + 1         # "더 큰 값도 가능한지 확인해보자!" (오른쪽 탐색)
        else:
            right = mid - 1        # 조건을 만족하지 못하므로 크기를 줄여야 함 (왼쪽 탐색)
            
    return best_answer

def check_condition(value):
    # 문제의 요구사항에 맞춰 value를 가공했을 때 나오는 결과값을 반환 (O(N) 탐색 등)
    pass

🚨 설계 및 회고

• Off-by-one Error 방어: 무한 루프에 빠지는 것을 막기 위해 left = mid나 right = mid가 아닌, 반드시 + 1, - 1을 해줌으로써 탐색 공간을 확실하게 축소시켜야 합니다.
• 정답 기록 시점 (best_answer): 조건을 만족할 때마다 best_answer에 값을 덮어씌워 두면, while 문이 끝난 후 고민할 필요 없이 가장 최적화된 경계값이 안전하게 남아있게 됩니다.

🚨 [심화 회고] 파라메트릭 서치: 왜 ==로 찾지 않고 부등호로 찾을까?

🤔 의문점: 이분 탐색에서 조건을 만족(target_condition)했을 때 바로 return하지 않고, 왜 부등호(>=, <=)를 사용하며 best_answer에 값을 덮어씌우고 계속 탐색할까? ==로 딱 떨어지는 값을 찾으면 연산이 훨씬 줄어들지 않을까?

💡 깨달음:
1. 정확한 값이 존재하지 않을 수 있다: 파라메트릭 서치는 '딱 맞는 값'을 찾는 것이 아니라, '조건을 만족하는 최댓값(또는 최솟값)'을 찾는 최적화 문제다. 예를 들어 랜선을 105cm로 자르면 11조각, 106cm로 자르면 9조각이 나오는 경우, 정확히 10조각이 나오는 길이는 존재하지 않는다. 이때는 조건을 만족하는(10개 이상) 선에서 가장 최댓값인 105cm를 찾아야 하므로 부등호가 필수적이다.
2. best_answer의 진짜 역할 (Checkpoint 🎯): 조건을 만족했다고 바로 탐색을 멈추면, 그 값이 우리가 낼 수 있는 '최고의 한계치(최댓값)'라는 보장이 없다. 따라서 best_answer에 현재 값을 '안전망'으로 기록해 두고, 포인터(left, right)를 조절하여 한계치까지 계속 욕심을 내어 탐색을 이어가야 한다. while문이 완전히 종료된 후 남아있는 값이 가장 완벽한 최적의 경계값이 된다.