5강 / 20강

이진 탐색 — 100만 개를 20번에

정렬해 두면 절반씩 버릴 수 있다

국어사전에서 '알고리즘'을 찾을 때, 여러분은 1페이지부터 넘기지 않습니다. 대충 가운데를 펴고 "아, 여기는 'ㅅ'이네, 그럼 앞쪽" 하며 절반을 버리죠.

이것이 이진 탐색(binary search)입니다. 한 번 볼 때마다 후보의 절반이 사라집니다.

📖

가운데를 본다

중간 값과 비교

✂️

절반을 버린다

범위가 반으로

🔁

반복한다

하나 남을 때까지

고등학생100만 개를 20번에

제목이 과장 같지만 사실입니다.

100만 개에서 하나를 찾는 데 20번이면 된다

어떻게 그럴 수 있나

절반씩 버리기 때문입니다.

단계	남은 개수
시작	1,000,000
1번	500,000
2번	250,000
10번	약 1,000
20번	1

한 번에 절반을 버리면 20번이면 끝난다

비유 — 숫자 맞히기 게임

1~100 중 하나를 맞힙니다. "더 큽니다/작습니다" 만 들을 수 있어요.

가장 빠른 방법은? 가운데를 부르는 겁니다.

50 → 75 → 62 → 68 → … 7번이면 맞힌다

1부터 하나씩 부르면 최대 100번이죠. 14배 차이입니다.

사전 찾기도 같습니다

사전에서 단어를 찾을 때 첫 장부터 넘기지 않죠. 가운데를 펴고, 앞인지 뒤인지 보고, 또 가운데를 폅니다.

여러분은 이미 이진 탐색을 할 줄 안다

이 강의는 그걸 코드로 쓰는 법을 배우는 겁니다.

고등학생단, 절대 조건이 하나 있습니다

note 가 결정적인 조건을 말합니다.

정렬되어 있어야 한다

왜 필요한가

이진 탐색은 "가운데보다 크니까 뒤쪽에 있겠다" 라고 판단합니다.

그런데 정렬이 안 되어 있으면 그 판단이 아무 근거가 없어요.

뒤죽박죽이면 어디에 있을지 알 수 없다

비유 — 정리 안 된 사전

단어가 아무렇게나 배열된 사전이 있다고 합시다. 가운데를 폈는데 '가방' 이 나왔어요.

내가 찾는 '나무' 는 앞일까요 뒤일까요? 알 수 없습니다. 그냥 전부 뒤져야 해요.

정렬은 이진 탐색의 선택이 아니라 전제다

그런데 정렬도 공짜가 아닙니다

6강에서 배울 텐데, 정렬에 O(n log n) 이 듭니다.

상황	유리한 방법
한 번만 찾는다	선형 탐색 — 정렬 비용이 아깝다
여러 번 찾는다	정렬 + 이진 탐색

한 번 정렬해 두면 이후 검색이 전부 빨라진다

퀴즈가 이걸 묻습니다. 한 번만 검색할 거면 정렬하지 않는 게 낫습니다.

🎮 이진 탐색 실험실

정렬된 주문번호 목록에서 하나를 찾아 봅시다. ▶ 한 걸음을 누를 때마다 회색으로 버려지는 절반을 보세요. 아래쪽에는 선형 탐색과 비교 횟수가 나란히 표시됩니다.

10만 건을 17걸음에. 직접 실행해 확인해 보세요.

Python 브라우저에서 실행

def 이진탐색(정렬된목록, 찾을것):
    lo, hi = 0, len(정렬된목록) - 1
    걸음 = 0
    while lo <= hi:
        걸음 += 1
        mid = (lo + hi) // 2            # 가운데
        if 정렬된목록[mid] == 찾을것:
            return mid, 걸음
        elif 정렬된목록[mid] < 찾을것:
            lo = mid + 1                # 왼쪽 절반을 통째로 버림
        else:
            hi = mid - 1                # 오른쪽 절반을 통째로 버림
    return -1, 걸음


주문번호들 = list(range(1000, 1000 + 100000))   # 정렬된 10만 건

for 목표 in (1000, 50000, 100999, 99999999):
    위치, 걸음 = 이진탐색(주문번호들, 목표)
    상태 = f"{위치}번 자리" if 위치 >= 0 else "없음"
    print(f"{목표:>9} → {상태:<10} {걸음:>2}걸음")

print()
print("10만 건인데 최대 17걸음. 선형 탐색이었다면 최악 100,000걸음입니다.")

왜 O(log n)일까요

매번 절반이 사라지니까, 몇 번 반으로 나누면 1이 되는가가 걸음 수입니다.

데이터 개수 n	선형 탐색 (최악)	이진 탐색 (최악)
100	100번	7번
1,000	1,000번	10번
100,000	100,000번	17번
1,000,000	1,000,000번	20번
1,000,000,000	10억 번	30번

맨 아래를 보세요. 데이터가 1,000배 늘어도 걸음은 10번만 늘어납니다. 이것이 O(log n)의 힘이에요. 데이터가 커질수록 이 차이는 더 벌어집니다.

log2(n)이 곧 걸음 수입니다.

Python 브라우저에서 실행

import math

print(f"{'상품 수':>12} {'선형':>12} {'이진':>6}")
print("-" * 34)
for n in (10, 100, 1000, 10000, 100000, 1000000, 10000000):
    print(f"{n:>12,} {n:>12,} {math.ceil(math.log2(n)):>6}")

print()
print("이진 탐색의 걸음 수 = log2(n) 을 올림한 값입니다.")

고등학생쇼핑몰에서의 이진 탐색 = 데이터베이스 인덱스

note 가 실무와 연결합니다. 아주 중요한 연결이에요.

DB 의 인덱스가 곧 이진 탐색(비슷한 것)이다

인덱스가 뭔가

책 맨 뒤의 찾아보기와 같습니다.

책	데이터베이스
본문을 처음부터 읽기	전체 훑기 (O(n))
찾아보기에서 쪽수 찾기	인덱스 (O(log n))

인덱스는 미리 정렬해 둔 목록이다

그래서 이런 일이 생깁니다

서비스가 커지면서 "주문 조회가 느립니다" 신고가 옵니다.

퀴즈가 묻죠 — 가장 먼저 확인할 것은?

그 열에 인덱스가 있는가

없으면 DB 가 전체를 훑고 있는 겁니다. 인덱스를 하나 만들면 극적으로 빨라져요.

그런데 인덱스도 공짜가 아닙니다

얻는 것	내주는 것
검색이 빨라진다	저장 공간을 더 쓴다
	쓰기가 느려진다 (인덱스도 갱신)

읽기를 빠르게 하려고 쓰기를 느리게 한 것

그래서 모든 열에 인덱스를 다는 건 나쁜 생각입니다. 자주 찾는 열에만 답니다.

/db 강의가 이 이야기를 제대로 다룹니다.

이진 탐색이 안 되는 경우

정렬이 안 됨 — 이진 탐색의 전제가 깨집니다. 답이 틀리게 나와요.
부분 일치 검색 — "이어폰이 들어간 상품"은 정렬로 못 찾습니다. (이건 전문 검색 엔진의 영역이에요.)
데이터가 계속 바뀜 — 정렬 상태를 유지하는 데 비용이 듭니다. 삽입이 아주 잦으면 해시가 낫습니다 (8강).

정렬은 이진 탐색의 '선택'이 아니라 '전제'입니다.

Python 브라우저에서 실행

# 정렬 안 된 목록에 이진 탐색을 쓰면? — 있는 것도 못 찾습니다
def 이진탐색(a, x):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == x: return mid
        elif a[mid] < x: lo = mid + 1
        else: hi = mid - 1
    return -1

정렬됨   = [10, 20, 30, 40, 50, 60, 70]
안정렬됨 = [40, 10, 70, 30, 60, 20, 50]     # 같은 값들, 순서만 뒤죽박죽

print("정렬된 목록에서 70 찾기  :", 이진탐색(정렬됨, 70), "  ← 찾음")
print("안 정렬된 목록에서 70 찾기:", 이진탐색(안정렬됨, 70), " ← 있는데 못 찾음! 🚨")
print()
print("70은 분명히 목록 안에 있습니다:", 70 in 안정렬됨)

고등학생파이썬에는 이미 들어 있습니다

note 가 솔직하게 말합니다 — 직접 짤 필요가 없다고요.

bisect 모듈이 이미 있다

그럼 왜 배우나

/py 8강에서 본 그 이야기입니다.

쓸 줄 아는 것과 왜 되는지 아는 것은 다르다

모르면	알면
왜 정렬이 필요한지 모른다	조건을 챙긴다
느릴 때 원인을 못 찾는다	인덱스를 의심한다
비슷한 문제에 응용 못 한다	"절반씩 줄이기" 를 다른 데 쓴다

세 번째가 진짜 이득이다

'절반씩 줄이기' 는 여기저기 쓰입니다

어디	어떻게
디버깅	코드를 절반씩 잘라 오류 위치 찾기
`git bisect`	커밋을 절반씩 짚어 버그가 언제 생겼는지
문제 풀이	답의 범위를 절반씩 좁히기

알고리즘은 생각하는 방법이기도 하다

직접 짜 볼 때의 함정

이진 탐색은 짧은데 틀리기 쉬운 것으로 유명합니다.

가운데를 어떻게 구할까 ((lo+hi)//2)
범위를 어디까지 줄일까 (hi = mid? mid-1?)
언제 멈출까 (lo < hi? lo <= hi?)

유명한 이야기로, 20년 동안 표준 라이브러리에 이진 탐색 버그가 숨어 있던 적도 있습니다.

단순해 보이는 것이 가장 틀리기 쉽다

🤔 확인 문제

정렬된 상품 100만 개에서 이진 탐색으로 하나를 찾을 때 최악 비교 횟수는?

🤔 확인 문제

이진 탐색을 쓰기 위한 필수 전제 조건은?

🤔 확인 문제

"주문 조회가 느립니다"라는 신고를 받았을 때 시스템 관리자가 가장 먼저 확인할 것은?