02 — 이진 탐색

람다와 제네릭이 숫자 맞히기 게임을 하고 돌핀쌤이 옆에서 지켜보는 도입 장면. 제네릭이 "1부터 100 중에 하나 정했어!"라고 말하는 분위기

🙋‍♂️ 제네릭: "내가 1부터 100 중에 숫자 하나를 정했어. 람다야, 맞혀 봐!"

🙋‍♀️ 람다: "100개를 하나씩 다 물어보면 너무 오래 걸리는데… 더 좋은 방법이 있을까요?"

🎯 오늘 완성할 코드는?

오늘 우리가 만들 건 이진 탐색이에요. 정렬된 리스트에서 찾는 값이 몇 번째 칸(인덱스) 에 있는지 빠르게 찾아내는 코드예요.

먼저 완성된 모습부터 볼게요. 지금은 이해 안 돼도 괜찮아요. 아래에서 한 줄씩 천천히 뜯어볼 거예요.

boxes = [2, 5, 8, 12, 16, 23, 38, 45, 56, 72]   # 정렬된 리스트
target = 23
left = 0                          # 맨 왼쪽 인덱스
right = len(boxes) - 1            # 맨 오른쪽 인덱스
ans = -1                          # 못 찾으면 -1
while left <= right:
    mid = (left + right) // 2     # 가운데 인덱스 (괄호 꼭!)
    if boxes[mid] == target:
        ans = mid                 # 찾았으니 인덱스 저장
        break
    elif boxes[mid] < target:     # 찾는 값이 더 크면
        left = mid + 1            # 왼쪽 절반 버리기
    else:                         # 찾는 값이 더 작으면
        right = mid - 1           # 오른쪽 절반 버리기
print(ans)   # 5

실행하면 이렇게 나와요.

23 은 리스트에서 5번 칸(인덱스 5)에 있어요. 그래서 5 가 나온 거예요.

🐬 돌핀쌤: "10줄 남짓한 짧은 코드지만, 이 안에 빠른 탐색의 핵심이 다 들어 있어요. 지금부터 이 코드가 왜 그렇게 빨리 찾는지 하나씩 풀어볼게요. 다 보고 나면 위 코드가 술술 읽힐 거예요."

💡 어떻게 풀까? — 가운데를 보고 절반을 버리기

지난 시간엔 보물 상자를 1번부터 하나씩 열어서 찾았어요(선형 탐색). 오늘은 훨씬 빨리 찾아볼게요.

제네릭이 정한 숫자는 37이에요. 람다가 이렇게 맞혀 봤어요.

50? → "더 작아!"   →  이제 1~49 사이구나
25? → "더 커!"     →  이제 26~49 사이구나
37? → "맞았어!"    →  단 3번 만에!

하나씩 물어봤다면 37번이나 걸렸을 텐데, 가운데를 물어보고 절반을 버리니까 단 3번이면 끝났어요.

🐬 돌핀쌤: "이렇게 가운데를 확인하고 범위를 절반씩 줄이는 방법을 이진 탐색이라고 해요. '이진'은 '둘로 나눈다'는 뜻이에요."

단, 한 가지 약속이 있어요. 리스트가 반드시 정렬(작은 값 → 큰 값 순서)되어 있어야 해요. 정렬돼 있어야 "가운데보다 크면 무조건 오른쪽"이라고 자신 있게 말할 수 있거든요. 맨 위 코드의 boxes 도 작은 수부터 큰 수 순서로 정렬돼 있죠?

🙋‍♀️ 람다: "뒤죽박죽이면 '오른쪽에 있다'고 확신할 수 없으니까, 그땐 지난번 선형 탐색을 써야 하는 거군요!"

🔍 코드 한 줄씩 뜯어보기

이제 맨 위에서 본 완성 코드를 한 줄씩 볼게요.

① 탐색 범위를 가리키는 세 인덱스: left · right · mid

left = 0                       # 탐색 범위의 맨 왼쪽 인덱스
right = len(boxes) - 1         # 탐색 범위의 맨 오른쪽 인덱스

이진 탐색은 세 개의 인덱스로 범위를 표시해요. left 는 범위의 왼쪽 끝, right 는 오른쪽 끝이에요. 칸이 10개면 인덱스는 0~9니까 right 는 len(boxes) - 1 = 9 로 시작해요.

② 가운데(mid)를 계산해요

    mid = (left + right) // 2     # 가운데 인덱스 (괄호 꼭!)

left 와 right 의 가운데가 mid 예요. 여기서 // 는 나눗셈의 몫(소수점 아래는 버림)이에요.

💡 인덱스(칸 번호)는 정수여야 해요. (0 + 9) // 2 는 4.5가 아니라 4 가 돼요. 그래서 /(4.5) 대신 //(4)를 써요. 그리고 괄호로 묶어야 left + right 를 먼저 더해요.

③ 가운데를 확인하고 절반을 버려요

    if boxes[mid] == target:
        ans = mid                 # 찾았으니 인덱스 저장
        break
    elif boxes[mid] < target:     # 찾는 값이 더 크면
        left = mid + 1            # 왼쪽 절반 버리기
    else:                         # 찾는 값이 더 작으면
        right = mid - 1           # 오른쪽 절반 버리기

가운데 값(boxes[mid])을 찾는 값(target)과 비교해요.

같으면 → 찾았어요! 인덱스를 저장하고 break 로 멈춰요.
가운데가 더 작으면 → 정답은 오른쪽에 있어요. left = mid + 1 로 왼쪽 절반을 버려요.
가운데가 더 크면 → 정답은 왼쪽에 있어요. right = mid - 1 로 오른쪽 절반을 버려요.

🐬 돌핀쌤: "mid 는 이미 확인했으니까 다음 범위에서 빼줘요. 그래서 mid + 1, mid - 1 처럼 mid를 건너뛰고 한 칸 옮기는 거예요. left = mid 처럼 그대로 두면 같은 칸을 계속 봐서 멈추지 않을 수 있어요."

④ `while left <= right` 의 등호가 중요해요

while left <= right:

조건에 등호(<=) 를 꼭 넣어야 해요. left == right 일 때, 즉 범위에 칸이 딱 1개 남았을 때도 확인해야 하거든요. < 만 쓰면 마지막 한 칸을 놓치고 "없어요"가 나올 수 있어요.

⑤ 전체가 어떻게 굴러가는지 — `23` 찾기

인덱스:  0   1   2    3    4    5    6    7    8    9
리스트: [2,  5,  8,  12, 16, 23, 38, 45, 56, 72]

단계	left	right	mid	boxes[mid]	판단
1	0	9	4	16	16 < 23 → 오른쪽, `left = 5`
2	5	9	7	45	45 > 23 → 왼쪽, `right = 6`
3	5	6	5	23	23 == 23 → 찾았어요!

탐색 범위가 10칸 → 5칸 → 2칸 으로 절반씩 줄어들죠? 단 3번 만에 인덱스 5 를 찾았어요.

🙋‍♂️ 제네릭: "가운데를 한 번 볼 때마다 후보가 절반으로 줄어드네요. 그래서 이렇게 빠른 거군요!"

✍️ 직접 완성해보기

이제 빈칸을 채워 직접 완성해봐요. 위에서 본 그대로예요.

boxes = [2, 5, 8, 12, 16, 23, 38, 45, 56, 72]   # 정렬된 리스트
target = 23
left = 0
right = len(boxes) - 1
ans = -1
while left <= right:
    mid = (left + right) ___ 2    # 가운데 인덱스 (// 사용)
    if boxes[mid] == target:
        ans = mid
        ___                       # 찾았으니 멈추기 (break)
    elif boxes[mid] ___ target:   # 찾는 값이 더 크면
        left = mid + ___          # 왼쪽 절반 버리기
    else:
        right = mid - 1           # 오른쪽 절반 버리기
print(ans)   # 5

🐬 돌핀쌤: "막히면 위 '코드 한 줄씩 뜯어보기'로 다시 올라가서 확인해요. 다 채웠으면 맨 위 🎯 완성 코드와 비교해보세요. 정답을 외우는 게 아니라 왜 그런지 떠올리는 게 진짜 공부예요."

📌 오늘 배운 것

개념	설명
이진 탐색	정렬된 리스트의 가운데를 보고 범위를 절반씩 줄이는 탐색
전제 조건	리스트가 반드시 정렬되어 있어야 함
left · right · mid	탐색 범위의 왼쪽·오른쪽·가운데 인덱스
mid 계산	`(left + right) // 2` (괄호 필수, 몫 `//` 사용)
while 조건	`left <= right` (마지막 1칸도 확인)
범위 줄이기	`left = mid + 1` / `right = mid - 1` (mid는 건너뜀)

🐬 돌핀쌤: "정렬·가운데·절반 버리기! 이 세 박자면 아무리 긴 리스트에서도 빠르게 찾을 수 있어요. 잘했어요! 👏"

▸ 더 해보기 — 여기서부터는 선택!

여기까지가 오늘의 필수 내용이에요. 아래는 여유 있을 때 도전하는 내용이고, 예제 문제로 직접 풀어볼 수 있어요. 외울 필요는 없어요.

없는 값 찾기 — target 을 리스트에 없는 값(예: 100)으로 바꾸면 ans 가 끝까지 -1 로 남아요. "없으면 -1"이 어떻게 동작하는지 확인해봐요. → 예제로 연습
다른 값 찾아보기 — target 을 72 나 2 로 바꿔서 맨 끝·맨 앞 값도 잘 찾는지 확인해봐요. → 예제로 연습
단계별 출력 — while 안에서 print(left, right, mid) 를 찍으면 범위가 절반씩 줄어드는 과정을 눈으로 볼 수 있어요.

🐬 돌핀쌤: "기본을 완벽히 익힌 다음 도전하세요. 전부 같은 뼈대 위에서 값만 바꿔보는 거예요."

참고 — 왜 이렇게 빠를까? (O(log n))

이진 탐색은 매번 절반을 버리니까, 리스트가 아무리 길어도 확인 횟수가 아주 적어요.

리스트 길이 (n)	선형 탐색 (최악)	이진 탐색 (최악)
8	8번	3번
1,024	1,024번	10번
1,000,000	1,000,000번	20번
1,000,000,000	10억 번	30번

리스트가 10억 칸이어도 이진 탐색은 30번이면 찾아요! 이걸 O(log n) ('오 로그 엔'이라고 읽어요)이라고 해요. 지금은 '절반씩 줄일 수 있는 횟수' 라고 기억하면 충분해요.

선형 탐색(O(n))과 이진 탐색(O(log n))의 확인 횟수 증가를 비교하는 곡선 그래프

02 — 이진 탐색

📃 해결할 문제

💻 예제 입력 1

🖨️ 예제 출력 1