[백준/Python] 1920번 수 찾기 - 순수 이분 탐색(Standard Binary Search) 뼈대 세우기

학습 철학 회고
본격적인 알고리즘 딥 워크(CPU Overclocking)에 들어가기 전, 뇌를 예열(Cache Loading)하기 위해 가장 기본적이고 순수한 형태의 이분 탐색 뼈대를 백지에서 구현해 보았습니다. 어제 학습한 '파라메트릭 서치(Parametric Search)'와 무엇이 다른지 그 본질적 차이를 몸으로 체화하는 과정이었습니다.

📌 문제 요약: 1920번 수 찾기

$N$개의 정수가 주어져 있을 때, 이 안에 $X$라는 정수가 존재하는지 알아내는 가장 기본적인 탐색 문제입니다.

• $N$과 $M$이 최대 100,000이므로, 배열을 매번 선형 탐색($O(N)$)하게 되면 $O(NM)$으로 무조건 시간 초과가 발생합니다.
• 따라서 데이터를 한 번 정렬해 둔 뒤($O(N \log N)$), 절반씩 탐색 범위를 날려버리는 이분 탐색($O(\log N)$)을 $M$번 수행하여 $O(N \log N + M \log N)$의 시간 복잡도로 방어해야 합니다.

💻 실전 조립 코드 (SOP 적용 및 미세 최적화)

import sys
input = sys.stdin.readline

def binary_search(A, target):
    # 1. 탐색 공간 설정: 배열의 '인덱스' 양끝점
    start = 0
    end = len(A) - 1

    # 2. start와 end가 교차하기 전까지 반복
    while start <= end:
        mid = (start + end) // 2
        
        # 3. [핵심] 찾고자 하는 값을 정확히 발견한 경우 (Early Return)
        if A[mid] == target:
            return 1 
            
        # 4. 타겟이 더 크다면 오른쪽 탐색 (start를 mid 위로 끌어올림)
        elif A[mid] < target:
            start = mid + 1
            
        # 5. 타겟이 더 작다면 왼쪽 탐색 (end를 mid 아래로 끌어내림)
        else:
            end = mid - 1

    # 무한 루프를 다 돌았는데도 return 되지 않았다면 없는 것
    return 0

def solution():
    N = int(input())
    A = list(map(int, input().split()))
    M = int(input())
    B = list(map(int, input().split()))

    # [치명적 실수 방어] 탐색 루프에 들어가기 전, 반드시 딱 한 번만 정렬!
    A.sort()

    for target in B:
        print(binary_search(A, target))

if __name__ == "__main__":
    solution()

🚨 트러블 슈팅 및 심화 회고

순수 이분 탐색을 구현하며 정립한 3가지 핵심 엔지니어링 포인트입니다.

1. 순수 이분 탐색 vs 파라메트릭 서치
이 코드는 파라메트릭 서치가 아닙니다. 파라메트릭 서치는 딱 떨어지는 정답이 없어 부등호(>=)를 쓰고, best_answer라는 안전망을 두며 '최적의 조건'을 찾는 방식입니다. 반면, 이 문제는 A[mid] == target으로 '정확히 일치하는 값'을 찾으면 바로 탈출하는 전형적인 '순수 이분 탐색(Standard Binary Search)'입니다.

2. 정렬(sort())의 생명주기 통제
가장 흔하게 하는 치명적 실수가 sort()를 탐색 함수 안이나 쿼리를 도는 for문 안에 넣는 것입니다. 매 탐색마다 정렬을 수행하면 시간 복잡도가 폭발합니다. A.sort()를 입력 직후 단 한 번만 수행하여 생명주기를 완벽하게 통제했습니다.

3. 상태 변수와 break를 제거한 Early Return 구조
초기 코드에서는 answer = 1로 상태를 기록하고 break를 건 뒤 마지막에 return answer를 했습니다. 하지만 파이썬에서는 불필요한 상태 변수를 두지 않고, 타겟을 찾은 즉시 함수 자체를 탈출하는 return 1을 사용하면 코드가 훨씬 간결해지고 유지보수가 쉬워집니다.