Python 알고리즘

Python의 이진 탐색(binary search)

이 레슨에서는 정렬된 리스트에서 값을 빠르게 찾는 이진 탐색을 구현합니다.

  • 중급
  • 2분 분량
  • 실행 가능한 예제 1개

소개

어떤 문제를 해결하나요

백만 개 항목의 리스트에서 값 하나를 하나씩 확인하며 찾으면 비교가 백만 번 걸릴 수 있습니다. 리스트가 정렬되어 있으면 훨씬 잘할 수 있습니다. 확인할 때마다 남은 것의 절반이 제외되므로 약 20번이면 충분합니다.

일상 속 비유

이진 탐색은 종이 사전에서 단어를 찾는 방법입니다. 가운데를 펼쳐 단어가 그 쪽보다 앞인지 뒤인지 보고, 단어가 있을 수 없는 절반을 버립니다. 단어에 닿을 때까지 남은 절반으로 반복합니다.

종이 사전에서 코드로
low, high = 0, len(values) - 1📖 아직 찾아야 할 쪽들
middle = (low + high) // 2👆 가운데 펼치기
low = middle + 1➡️ 단어가 더 뒤: 앞쪽 절반 버리기
high = middle - 1⬅️ 단어가 더 앞: 뒤쪽 절반 버리기
비교할 때마다 남은 것이 반으로 줄어, 거대한 리스트도 몇 단계면 됩니다.
한 문장으로

이진 탐색은 정렬된 리스트에서 값을 가운데 요소와 계속 비교하고 값이 있을 수 없는 절반을 버리며 찾으며, O(log n) 단계가 걸립니다.

핵심 포인트

  1. low 와 high 는 아직 목표가 있을 수 있는 리스트 부분을 표시합니다.
  2. middle = (low + high) // 2 는 그 부분의 가운데 인덱스를 고릅니다.
  3. values[middle] < target 이면 목표는 오른쪽에 있으므로 low = middle + 1, 아니면 high = middle - 1 입니다.
  4. while low <= high: 는 범위가 비면 멈추고, 함수는 없음을 뜻하는 -1 을 돌려줍니다.
  5. 17을 찾을 때는 12, 25, 17을 확인합니다. 네 번이 아니라 세 번 비교합니다.

언제 사용하나요?

  • 큰 정렬 데이터 검색: ID, 사전, 정렬된 로그.
  • 리스트가 정렬된 상태를 유지하도록 값을 넣을 위치 찾기.
  • 맞히기 게임처럼 더 크다, 작다로 답을 좁힐 수 있는 모든 문제.

필요 없는 경우

  • 정렬되지 않은 데이터: 한 번 찾으려고 정렬하면 선형 탐색보다 비쌉니다.
  • 작은 리스트나 한 번뿐인 조회: in 이나 딕셔너리가 더 간단하고, 키로 자주 찾는다면 dict 나 set 이 훨씬 빠릅니다.

Python의 이진 탐색(binary search) 시각화

O(log n)

재생 또는 한 단계를 눌러 비교와 데이터 이동 과정을 확인하세요.

예제 코드

코드 실행 →
main.py
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 컴파일러에서 실행하세요.

연습 문제

아래 제안을 따라 코드를 바꿔 보세요. 코드를 직접 고치고 결과를 확인하면 읽기만 할 때보다 레슨을 훨씬 잘 이해할 수 있습니다.

  1. 빈 리스트, 요소가 하나인 리스트, 중복이 있는 리스트로 테스트해 보세요.
  2. 단계마다 상태를 출력해서 알고리즘이 동작하는 모습을 살펴보세요.
  3. 요소 100개, 1,000개, 10,000개로 실행 시간을 재고 다른 방법과 비교해 보세요.
Python 컴파일러에서 실행 →

자주 하는 실수

반복문에서 <= 대신 < 쓰기

low < high 이면 마지막 남은 위치의 목표는 확인되지 않습니다.

문제
while low < high:
수정
while low <= high:

가운데를 넘어가지 않기

low = middle 은 같은 가운데를 영원히 반복할 수 있습니다.

문제
low = middle
수정
low = middle + 1

이 레슨을 마쳤나요?

학습 완료로 표시하면 진행 상황을 기록할 수 있습니다.

챌린지로 연습하기

이 레슨에서 배운 내용으로 실제 문제를 풀어 보세요. 모든 챌린지는 브라우저에서 실행되며 즉시 테스트와 AI 리뷰를 받을 수 있습니다.

모든 챌린지