Python의 이진 탐색(binary search)
이 레슨에서는 정렬된 리스트에서 값을 빠르게 찾는 이진 탐색을 구현합니다.
소개
어떤 문제를 해결하나요
백만 개 항목의 리스트에서 값 하나를 하나씩 확인하며 찾으면 비교가 백만 번 걸릴 수 있습니다. 리스트가 정렬되어 있으면 훨씬 잘할 수 있습니다. 확인할 때마다 남은 것의 절반이 제외되므로 약 20번이면 충분합니다.
일상 속 비유
이진 탐색은 종이 사전에서 단어를 찾는 방법입니다. 가운데를 펼쳐 단어가 그 쪽보다 앞인지 뒤인지 보고, 단어가 있을 수 없는 절반을 버립니다. 단어에 닿을 때까지 남은 절반으로 반복합니다.
low, high = 0, len(values) - 1📖 아직 찾아야 할 쪽들middle = (low + high) // 2👆 가운데 펼치기low = middle + 1➡️ 단어가 더 뒤: 앞쪽 절반 버리기high = middle - 1⬅️ 단어가 더 앞: 뒤쪽 절반 버리기이진 탐색은 정렬된 리스트에서 값을 가운데 요소와 계속 비교하고 값이 있을 수 없는 절반을 버리며 찾으며, O(log n) 단계가 걸립니다.
핵심 포인트
low와high는 아직 목표가 있을 수 있는 리스트 부분을 표시합니다.middle = (low + high) // 2는 그 부분의 가운데 인덱스를 고릅니다.values[middle] < target이면 목표는 오른쪽에 있으므로low = middle + 1, 아니면high = middle - 1입니다.while low <= high:는 범위가 비면 멈추고, 함수는 없음을 뜻하는-1을 돌려줍니다.- 17을 찾을 때는 12, 25, 17을 확인합니다. 네 번이 아니라 세 번 비교합니다.
언제 사용하나요?
- 큰 정렬 데이터 검색: ID, 사전, 정렬된 로그.
- 리스트가 정렬된 상태를 유지하도록 값을 넣을 위치 찾기.
- 맞히기 게임처럼 더 크다, 작다로 답을 좁힐 수 있는 모든 문제.
필요 없는 경우
- 정렬되지 않은 데이터: 한 번 찾으려고 정렬하면 선형 탐색보다 비쌉니다.
- 작은 리스트나 한 번뿐인 조회:
in이나 딕셔너리가 더 간단하고, 키로 자주 찾는다면 dict 나 set 이 훨씬 빠릅니다.
Python의 이진 탐색(binary search) 시각화
O(log n)재생 또는 한 단계를 눌러 비교와 데이터 이동 과정을 확인하세요.
예제 코드
def binary_search(values, target):
low, high = 0, len(values) - 1
while low <= high:
middle = (low + high) // 2
if values[middle] == target:
return middle
if values[middle] < target:
low = middle + 1
else:
high = middle - 1
return -1
print(binary_search([3, 8, 12, 17, 25, 31], 17))
실행 결과
3
코드 설명
변수 low와 high는 아직 찾아봐야 할 구간을 나타냅니다. 가운데 요소가 찾는 값보다 작으면 low = middle + 1로 왼쪽 절반을 버리고, 그렇지 않으면 오른쪽 절반을 버립니다. 시간 복잡도는 O(log n)이며, 입력 리스트가 이미 정렬되어 있어야 합니다.
값을 변경하고 Python 설치 없이 CodeUtility 온라인 Python 컴파일러에서 실행하세요.
연습 문제
아래 제안을 따라 코드를 바꿔 보세요. 코드를 직접 고치고 결과를 확인하면 읽기만 할 때보다 레슨을 훨씬 잘 이해할 수 있습니다.
- 빈 리스트, 요소가 하나인 리스트, 중복이 있는 리스트로 테스트해 보세요.
- 단계마다 상태를 출력해서 알고리즘이 동작하는 모습을 살펴보세요.
- 요소 100개, 1,000개, 10,000개로 실행 시간을 재고 다른 방법과 비교해 보세요.
자주 하는 실수
반복문에서 <= 대신 < 쓰기
low < high 이면 마지막 남은 위치의 목표는 확인되지 않습니다.
while low < high:
while low <= high:
가운데를 넘어가지 않기
low = middle 은 같은 가운데를 영원히 반복할 수 있습니다.
low = middle
low = middle + 1
이 레슨을 마쳤나요?
학습 완료로 표시하면 진행 상황을 기록할 수 있습니다.
챌린지로 연습하기
이 레슨에서 배운 내용으로 실제 문제를 풀어 보세요. 모든 챌린지는 브라우저에서 실행되며 즉시 테스트와 AI 리뷰를 받을 수 있습니다.
- 공장 생산 시간 병렬로 동작하는 기계들이 목표 개수의 제품을 가장 빨리 완성할 수 있는 시간을 구하세요. 보통
- Median of Two Sorted Arrays Find the median of two sorted lists combined. 어려움