16강 / 20강

탐색 — 처음부터 하나씩 vs 반씩 접기

정렬해 두면 찾기가 얼마나 빨라지는가

국어사전에서 '자료구조'를 찾는다고 합시다. 1쪽부터 한 장씩 넘기나요? 아니죠. 가운데를 펼치고, 'ㅈ'보다 앞이면 뒤쪽 절반을 버립니다. 이게 이진 탐색(binary search)이고, 이렇게 하려면 사전이 정렬되어 있어야 합니다.

🐌 선형 탐색

처음부터 하나씩 비교
정렬 필요 없음
1000개면 최대 1000번
O(n)

⚡ 이진 탐색

가운데와 비교 후 절반 버리기
정렬 필수
1000개면 최대 10번
O(log n)

고등학생처음부터 하나씩 vs 반씩 접기

가장 기본적인 두 가지 찾기 방법입니다.

방법	조건	비교 횟수
선형 탐색	없다	n
이진 탐색	정렬돼야 한다	log n

조건이 붙는 대신 어마어마하게 빨라진다

이진 탐색이 하는 일

가운데를 본다
찾는 값보다 크면 오른쪽 절반을 버린다
작으면 왼쪽 절반을 버린다
반복

한 번 비교에 절반이 사라진다

비유 — 사전에서 단어 찾기

"마늘" 을 찾을 때 1쪽부터 넘기나요?

아니죠. 중간을 펴고 앞인지 뒤인지 봅니다. 그리고 또 그 절반의 중간을 펴고요.

쪽수	펴 보는 횟수
1,000쪽	10번

아무도 사전을 1쪽부터 넘기지 않는다 — 이미 이진 탐색을 하고 있다

11강의 BST 와 같은 원리입니다

구조	절반을 버리는 근거
정렬된 리스트	순서
BST	트리 규칙

둘 다 "규칙이 있으니 안 봐도 안다" 는 발상

1000개 중 맨 끝 값 찾기. 비교 횟수를 직접 세어 봅니다.

Python 브라우저에서 실행

def 선형탐색(목록, 값):
    for ㅇ, ㅂ in enumerate(목록):
        if ㅂ == 값:
            return ㅇ, ㅇ + 1        # 위치, 비교 횟수
    return -1, len(목록)

def 이진탐색(목록, 값):               # 목록은 반드시 정렬되어 있어야 합니다
    왼, 오, 횟수 = 0, len(목록) - 1, 0
    while 왼 <= 오:
        횟수 += 1
        가운데 = (왼 + 오) // 2
        if 목록[가운데] == 값:
            return 가운데, 횟수
        elif 목록[가운데] < 값:
            왼 = 가운데 + 1           # 왼쪽 절반 통째로 버림
        else:
            오 = 가운데 - 1           # 오른쪽 절반 통째로 버림
    return -1, 횟수

값들 = list(range(0, 2000, 2))        # 0, 2, 4 … 1998 (1000개, 정렬됨)
찾을값 = 1998                          # 일부러 맨 끝

위치1, 횟수1 = 선형탐색(값들, 찾을값)
위치2, 횟수2 = 이진탐색(값들, 찾을값)
print(f"선형 탐색: {위치1}번 자리, 비교 {횟수1}번")
print(f"이진 탐색: {위치2}번 자리, 비교 {횟수2}번")
print(f"→ {횟수1 // 횟수2}배 적게 비교했습니다")

🎮 반씩 접히는 과정 보기

찾을 값을 정하고 한 걸음씩 눌러 보세요. 버려지는 절반이 회색으로 사라집니다. 아래 막대는 선형 탐색과 이진 탐색의 비교 횟수를 나란히 보여 줍니다.

고등학생이진 탐색의 함정

이진 탐색은 쓰기 어려운 것으로 유명합니다.

유명한 이야기 — 첫 논문 이후 20년이 지나서야 올바른 코드가 나왔다

왜 어려운가 — 경계 문제

정할 것	선택지
범위 끝	`right = n` 인가 `n-1` 인가
조건	`while l < r` 인가 `<=` 인가
줄이기	`r = mid` 인가 `mid-1` 인가

조합이 여덟 가지 — 맞는 조합은 몇 개뿐

틀리면 이렇게 됩니다

증상	원인
무한 루프	범위가 안 줄어든다
못 찾는다	마지막 하나를 건너뛴다
범위 초과	끝 처리가 틀렸다

대부분의 자료에서 잘 돌다가 특정 경우에 틀린다

그래서 실무에서는

import bisect
i = bisect.bisect_left(정렬된목록, 값)

직접 짜지 말고 이미 있는 것을 쓴다 — 17강의 조언과 같다

비유 — 자를 대고 자르기

종이를 정확히 반으로 자르는 건 쉬워 보입니다. 그런데 정확히 반이 되게 하려면?

1mm 씩 어긋나다 보면 마지막에 안 맞아요.

아이디어는 단순한데 정확히 구현하는 게 어렵다

이게 프로그래밍의 흔한 모습입니다. "알겠다" 와 "짤 수 있다" 는 다릅니다.

log₂ 라는 마법

이진 탐색은 한 번 비교할 때마다 후보가 절반이 됩니다.

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

데이터가 1000배가 되어도 비교는 10번만 늘어납니다. 이게 O(log n)이에요.

고등학생log₂ 라는 마법

note 가 감탄하는 로그를 손으로 느껴 봅시다.

log₂ n = n 을 몇 번 반으로 접어야 1이 되나

표로 보면

n	log₂ n
2	1
1,024	10
100만	20
10억	30
1조	40

자료가 1000배 늘어도 비교는 10번만 는다

이게 왜 마법인가

거꾸로 보면 더 놀랍습니다.

비교 횟수를 1 늘리면	다룰 수 있는 양
+1	2배
+10	1000배

일을 조금 더 하면 엄청나게 큰 자료를 다룬다

비유 — 종이 접기

종이를 42번 접으면 두께가 달까지 갑니다. (실제로는 못 접지만 계산상으로요.)

접는 횟수	두께
10	약 10cm
20	100m
30	100km
42	달

반씩 곱하기와 반씩 나누기는 같은 힘이다 — 방향만 반대

그래서 log 가 나오면 안심해도 됩니다

복잡도	실전에서
O(log n)	사실상 상수 — 걱정 없다
O(n log n)	충분히 빠르다
O(n²)	조심해야 한다

19강에서 이 감각을 제대로 정리한다

log 의 위력을 숫자로 실감해 봅니다.

Python 브라우저에서 실행

import math

for ㄴ in [100, 10_000, 1_000_000, 1_000_000_000]:
    print(f"{ㄴ:>15,}개 → 선형 최대 {ㄴ:>15,}번 | 이진 최대 {math.ceil(math.log2(ㄴ)):>3}번")

print()
print("종이를 몇 번 접으면 달까지 닿을까? — 같은 원리입니다.")
두께 = 0.1          # mm
거리 = 384_400_000_000   # mm
횟수 = 0
while 두께 < 거리:
    두께 *= 2
    횟수 += 1
print(f"0.1mm 종이를 {횟수}번만 접으면 달에 닿습니다. 절반씩 줄이는 것도 이만큼 강력해요.")

고등학생정렬 비용을 잊지 마세요

note 의 이 경고가 실전 판단을 가릅니다.

이진 탐색은 빠르지만 정렬이 먼저 필요하다

계산해 봅시다

방법	비용
선형 탐색 한 번	n
정렬 + 이진 탐색 한 번	n log n + log n

한 번만 찾을 거면 정렬이 손해다

몇 번부터 이득인가

검색 횟수 k	선형	정렬 후 이진
1	n	n log n ⚠
log n 쯤	비슷	비슷
많다	k·n	n log n + k log n ✔

여러 번 찾을수록 정렬해 두는 것이 이득

비유 — 책상 정리

책을 한 권 찾으려고 책장을 전부 정리하나요?

상황	판단
한 권만 찾는다	그냥 뒤진다
매일 찾는다	정리한다 ✔

정리는 투자다 — 여러 번 쓸 때 회수된다

그런데 세 번째 선택지가 있습니다

방법	준비	검색
선형	0	O(n)
정렬 + 이진	O(n log n)	O(log n)
집합/딕셔너리	O(n)	O(1) ✔

"있나 없나" 만 물을 거면 해시가 이긴다 (13강)

정렬이 필요한 건 순서나 범위가 필요할 때예요. 단순 검색이면 집합이 낫습니다.

20강의 물음이 여기서도 — 무엇을 자주 하느냐

bisect — 직접 만들 필요 없이 이미 준비되어 있습니다.

Python 브라우저에서 실행

import bisect

# 파이썬이 이미 이진 탐색을 제공합니다
점수 = [64, 76, 82, 88, 91, 95, 100]

ㅇ = bisect.bisect_left(점수, 88)
print(f"88은 {ㅇ}번 자리에 있습니다")

# 정렬을 유지하면서 새 값 넣기
bisect.insort(점수, 85)
print("85를 넣은 뒤:", 점수)

# 등급 매기기 — 실전에서 아주 많이 쓰는 요령
경계 = [60, 70, 80, 90]
등급 = ["F", "D", "C", "B", "A"]
for ㅅ in [55, 65, 88, 95, 100]:
    print(f"{ㅅ:3}점 → {등급[bisect.bisect_right(경계, ㅅ)]}등급")

그런데 해시가 더 빠르지 않나요?

맞습니다. 13강의 해시 테이블은 비교조차 없이 즉시 찾습니다. 그럼 이진 탐색은 왜 배울까요?

해시는 "정확히 이 값"만 찾습니다. "85점 이상인 학생들"은 못 찾아요.
이진 탐색은 "가장 가까운 값", "이 값이 들어갈 자리"도 알려 줍니다.
해시는 순서가 없지만, 정렬된 배열은 순서 그 자체가 정보입니다.

속도만이 기준이 아닙니다. 이 이야기를 20강에서 마무리합니다.

🤔 확인 문제

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

🤔 확인 문제

100만 개짜리 정렬된 리스트에서 이진 탐색의 최대 비교 횟수는 약?

🤔 확인 문제

정렬되지 않은 데이터에서 값을 딱 한 번 찾아야 합니다. 가장 합리적인 방법은?