Ch.8 정렬과 탐색

Binary Search — 반씩 줄이는 탐색

Binary Search의 동작 원리와 O(log n) 유도 과정을 설명한다off-by-one 에러 없이 Binary Search를 구현한다

100만 개 중에서 20번이면 찾는다?

사전에서 단어를 찾을 때 처음부터 넘기지 않습니다. 가운데를 펴고, 앞인지 뒤인지 판단합니다.

코드로 옮기면 경계값(lo, hi, mid) 처리가 항상 헷갈린다

불변식(invariant)을 유지하면 off-by-one 에러 없이 깔끔하게 구현할 수 있습니다.

lightbulb

핵심 개념

Binary Search

정렬된 배열에서 탐색 범위를 절반씩 줄이는 O(log n) 알고리즘

불변식(Invariant)

알고리즘 실행 중 항상 참인 조건

article

핵심 내용

정렬된 배열이라면 절반씩 줄일 수 있습니다

n = 1,000,000일 때 log₂(1,000,000) ≈ 20번 비교면 충분합니다

불변식: **target이 있다면 arr[lo..hi] 범위 안에 있다**

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    
    while lo <= hi:             # 불변식: target ∈ arr[lo..hi]
        mid = lo + (hi - lo) // 2  # 오버플로우 방지
        
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1        # 왼쪽 절반 제거
        else:
            hi = mid - 1        # 오른쪽 절반 제거
    
    return -1  # 찾지 못함

`mid = lo + (hi - lo) // 2`는 (lo + hi) // 2와 같지만 오버플로우를 방지합니다

[1, 3, 5, 7, 9, 11]에서 target=7을 찾는 과정입니다

6개 원소에서 3번 만에 찾았습니다. 선형 탐색이면 4번이었을 것

Binary Search의 90%는 경계값 실수에서 버그가 발생합니다

흔한 실수 3가지: 1. `while lo < hi` vs `while lo <= hi` — 등호 빠뜨림 2. `mid = (lo + hi) // 2` — 큰 수에서 오버플로우 3. `lo = mid` — 무한 루프 발생 가능

# 재귀 버전
def binary_search_rec(arr, target, lo=0, hi=None):
    if hi is None:
        hi = len(arr) - 1
    if lo > hi:
        return -1
    
    mid = lo + (hi - lo) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_rec(arr, target, mid + 1, hi)
    else:
        return binary_search_rec(arr, target, lo, mid - 1)

면접에서는 반복문 버전을 권장합니다 — 재귀 스택 O(log n) 추가 공간 없음

Python은 Binary Search를 내장 모듈로 제공합니다

import bisect

arr = [1, 3, 5, 7, 9, 11]

# 삽입 위치 찾기 (왼쪽)
bisect.bisect_left(arr, 7)    # → 3

# 삽입 위치 찾기 (오른쪽)
bisect.bisect_right(arr, 7)   # → 4

# 원소 존재 확인
def bs_contains(arr, target):
    i = bisect.bisect_left(arr, target)
    return i < len(arr) and arr[i] == target

면접에서 `bisect`를 쓸 수 있는지 먼저 확인하세요. 직접 구현을 요구하는 경우가 많습니다

길이 1024의 정렬된 배열에서 Binary Search로 최대 몇 번 비교하나요?

Binary Search는 정렬되지 않은 배열에도 사용할 수 있다

Binary Search 마스터!

key

핵심 용어

📐

전제 조건

배열이 정렬되어 있어야 함

🎯

핵심 아이디어

mid값과 비교하여 탐색 범위를 절반으로

⏱️

시간 복잡도

O(log n) — n=100만이면 20번

edit_note

정리 노트

Binary Search — 기본

핵심 개념

전제
정렬된 배열 필수
시간
O(log n) — n=100만이면 20번
불변식
target ∈ arr[lo..hi]

구현 주의점

while 조건
`lo <= hi` — 등호 빠뜨리지 말 것
mid 계산
`lo + (hi - lo) // 2` — 오버플로우 방지
Python
`bisect.bisect_left/right` 활용 가능
★

Binary Search를 쓸 수 있으면 '정렬 먼저 하고 bisect' 패턴을 고려하세요!

image

시각 자료

다이어그램: ds-d65
check_circle

핵심 정리

  • 1정렬된 배열 + 절반씩 줄이기 = O(log n)
  • 2불변식 유지로 경계값 실수 방지
  • 3Python bisect 모듈로 간결하게 구현 가능

퀴즈와 인터랙션으로 더 깊이 학습하세요

play_circle인터랙티브 레슨 시작