18. 이분 탐색 (Binary Search) — O(log n), 정렬된 배열 필수

핵심 인사이트 (3줄 요약)

1. 본질: 이분 탐색은 정렬된 배열에서 탐색 범위를 매 단계 절반으로 줄여 O(log n)에 목표값을 찾는 알고리즘으로, "분할 후 정복"의 가장 단순한 형태다.
2. 가치: O(log n)이라는 압도적 효율(n=10억에서 30번 비교)은 데이터베이스 인덱스, 컴파일러 심볼 테이블, 이분 탐색 트리의 이론적 근거를 제공한다.
3. 판단 포인트: off-by-one 버그(경계값 처리)가 가장 흔한 구현 오류이며, 하한(Lower Bound)/상한(Upper Bound) 변형을 통해 중복값 처리와 조건 최적화 문제에 응용된다.

Ⅰ. 개요 및 필요성

선형 탐색(Linear Search)은 n개 원소를 순차적으로 확인하여 O(n)이다. 데이터가 정렬되어 있다면, 중간값을 기준으로 탐색 범위를 절반으로 줄이는 **이분 탐색 (Binary Search)**으로 O(log n)을 달성할 수 있다.

선형 탐색 vs 이분 탐색

📢 섹션 요약 비유: 이분 탐색은 두꺼운 사전에서 단어 찾기와 같다. 무작위 페이지를 펼쳐서 찾는 단어보다 앞인지 뒤인지 판단하고, 절반씩 범위를 줄이면 어떤 단어도 몇 번만에 찾을 수 있다.

Ⅱ. 아키텍처 및 핵심 원리

기본 이분 탐색 구현

BinarySearch(arr, target):
  left = 0, right = n - 1
  while left <= right:
    mid = left + (right - left) / 2  ← 오버플로우 방지
    if arr[mid] == target: return mid
    elif arr[mid] < target: left = mid + 1
    else: right = mid - 1
  return -1  ← 찾지 못함

ASCII 다이어그램 — 탐색 과정

배열: [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
인덱스: 0  1  2  3  4   5   6   7   8   9
목표: 7

── 1단계 ──────────────────────────────────────
left=0, right=9, mid=4
arr[4]=9 > 7 → right = mid - 1 = 3
[1, 3, 5, 7] ← 탐색 범위 절반으로

── 2단계 ──────────────────────────────────────
left=0, right=3, mid=1
arr[1]=3 < 7 → left = mid + 1 = 2
      [5, 7] ← 탐색 범위 또 절반

── 3단계 ──────────────────────────────────────
left=2, right=3, mid=2
arr[2]=5 < 7 → left = mid + 1 = 3
         [7] ← 범위 1

── 4단계 ──────────────────────────────────────
left=3, right=3, mid=3
arr[3]=7 == 7 → 발견! 인덱스 3 반환 ✅

총 4단계 (log₂(10) ≈ 3.32, 올림 → 4)

시간/공간 복잡도

하한(Lower Bound) / 상한(Upper Bound)

중복값이 있을 때 특정 값의 첫 번째 위치 또는 마지막 위치 다음을 찾는 변형이다.

Lower Bound (lower_bound): target 이상의 첫 번째 위치
  → arr[mid] < target: left = mid + 1
  → arr[mid] >= target: right = mid  ← (right = mid-1 이 아님!)

Upper Bound (upper_bound): target 초과의 첫 번째 위치
  → arr[mid] <= target: left = mid + 1
  → arr[mid] > target: right = mid

예시: arr = [1, 2, 2, 2, 3, 4], target = 2
  lower_bound = 인덱스 1 (첫 번째 2)
  upper_bound = 인덱스 4 (3의 위치, 2 범위의 끝)
  2의 개수: upper_bound - lower_bound = 3

매개변수 탐색 (Parametric Search)

"조건을 만족하는 최대/최솟값"을 구할 때, 이분 탐색의 아이디어를 **해 공간(Answer Space)**에 적용하는 기법이다.

문제: "K명 이상 들어가는 가장 작은 버스 용량은?"
  → 버스 용량 x에 대해 "x로 K명 수용 가능한가?" 판단 함수 작성
  → 이분 탐색으로 최솟값 탐색 (단조 증가/감소 조건 필수)

📢 섹션 요약 비유: Lower/Upper Bound는 도서관에서 같은 제목의 책이 여러 권 있을 때, "첫 번째 책이 어디?"(Lower)와 "마지막 책 다음이 어디?"(Upper)를 찾는 것과 같다.

Ⅲ. 비교 및 연결

off-by-one 오류 방지

이분 탐색의 가장 흔한 버그는 경계값 처리 실수다.

이분 탐색 응용 비교

📢 섹션 요약 비유: 이분 탐색과 매개변수 탐색의 관계는 자 재는 방법과 같다. 자(이분 탐색)로 직접 크기를 재는 것이 기본이고, 자를 여러 번 대어 최적 크기를 찾는 것(매개변수 탐색)이 응용이다.

Ⅳ. 실무 적용 및 기술사 판단

실무 시나리오

시나리오 1 — 데이터베이스 인덱스: B-트리 인덱스의 각 노드 내 키 탐색
→ 페이지당 수백 개 키에 이분 탐색 → O(log n) 탐색 보장

시나리오 2 — 컴파일러 심볼 테이블: 정렬된 심볼 목록에서 변수명 탐색
→ 이분 탐색으로 O(log n) 조회

시나리오 3 — 이진 탐색 트리(BST): 이분 탐색의 구조화된 형태
→ 삽입/삭제가 가능한 동적 이분 탐색 구조

시나리오 4 — 업무 최적화 문제: "최소 배송 비용으로 D일 이내 전달 가능한가?"
→ 매개변수 탐색: 비용 x에 대해 판단 함수 설계 후 이분 탐색

기술사 구현 주의사항

┌──────────────────────────────────────────────────────┐
│  이분 탐색 구현 체크리스트                            │
│                                                      │
│  1. 전제 조건 확인: 배열이 정렬되어 있는가?           │
│  2. 인덱스 초기화: left=0, right=n-1 (기본 탐색)     │
│                    left=0, right=n (Lower/Upper Bound)│
│  3. mid 계산: left + (right-left)/2 (오버플로우 방지) │
│  4. 루프 조건: while left <= right (기본)            │
│                while left < right (Lower/Upper Bound) │
│  5. 업데이트: 항상 범위가 줄어드는지 확인            │
│  6. 반환값: -1 (미발견) vs lower_bound (삽입 위치)   │
└──────────────────────────────────────────────────────┘

📢 섹션 요약 비유: 이분 탐색 구현의 off-by-one은 마치 자물쇠 조합의 마지막 숫자 같다. 1999번까지 맞다가 2000번째 조합만 틀리면 문이 열리지 않는다.

Ⅴ. 기대효과 및 결론

이분 탐색은 알고리즘의 가장 우아한 아이디어 중 하나다. 단순한 탐색 알고리즘을 넘어, 매개변수 탐색을 통해 최적화 문제에까지 적용되며, 데이터베이스 인덱스와 자료구조의 이론적 토대를 제공한다.

효과 정리

📢 섹션 요약 비유: 이분 탐색은 전화번호부에서 "박○○"을 찾을 때 가장 전형적인 방법이다. 중간 페이지를 펼쳐서 "박" 앞이면 앞으로, 뒤면 뒤로 — 몇 번만 하면 10만 명 중에서도 찾을 수 있다.

📌 관련 개념 맵

📈 관련 키워드 및 발전 흐름도

[선형 탐색 (Linear Search) — O(n), 정렬 불필요]
    │
    ▼
[이분 탐색 (Binary Search) — O(log n), 정렬된 배열 필수]
    │
    ▼
[하한/상한 (Lower/Upper Bound) — 중복값 범위 탐색 변형]
    │
    ▼
[매개변수 탐색 (Parametric Search) — 해 공간 이분 탐색, 최적화 문제]
    │
    ▼
[이진 탐색 트리 (BST) / B-트리 — 동적 데이터 구조로 확장]

이분 탐색은 정렬된 배열에서 범위를 반으로 줄이는 분할 원리를 바탕으로, Lower/Upper Bound·매개변수 탐색·BST 등 다양한 알고리즘과 자료구조로 확장된다.

👶 어린이를 위한 3줄 비유 설명

📖 두꺼운 사전 찾기: '사과'를 찾을 때 가운데 페이지를 펼쳐서 '사과'가 앞인지 뒤인지 보고, 계속 반씩 줄이면 어떤 단어도 금방 찾을 수 있어요!
🎯 업다운 숫자 맞히기: 1~100 중 숫자를 맞힐 때 50, 25, 75 순으로 물으면 7번 만에 반드시 맞힐 수 있어요 — 이게 바로 이분 탐색이에요!
🔍 키 큰 순서 줄 서기: 이미 키 순으로 줄 서 있는 친구들 사이에서 내 자리를 찾을 때, 가운데 친구와 비교하면서 반씩 줄여가면 빠르게 찾을 수 있어요!