정렬된 목록에서 값 찾기 — 원문 해설

원문 해설 자료

학습 대상: 알고리즘을 처음 배우는 학생

1 탐색 범위를 절반씩 줄이는 binary_search

원문 코드

def binary_search(items, target):
    low, high = 0, len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            return mid
        if items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

binary_search는 low와 high로 아직 살펴볼 구간의 양 끝을 표시합니다. 반복할 때마다 가운데 위치 mid의 값을 target과 비교해, 같으면 그 위치를 돌려주고 더 작으면 오른쪽 절반, 더 크면 왼쪽 절반만 남깁니다. 비교 한 번에 후보가 절반으로 줄어들기 때문에 긴 목록에서도 몇 번의 비교로 끝납니다.

핵심 정리

• mid = (low + high) // 2는 남은 구간의 가운데 위치입니다.
• items[mid] < target이면 mid까지는 모두 target보다 작으므로 low = mid + 1로 버립니다.
• 끝까지 찾지 못하면 -1을 돌려줍니다.

본문 근거: S1 · 원문 줄: 6–16 · 설정 모델: 없음 — 직접 작성한 예시 · 생성: 2026-10-22T00:00:00.000Z

2 low > high가 되면 멈추는 이유

원문 발췌

low가 high보다 커지면 더 살펴볼 범위가 남지 않았다는 뜻이므로 값이 목록에 없습니다.
목록이 정렬되어 있지 않으면 이 방법은 올바른 위치를 보장하지 않습니다.

반복 조건 while low <= high는 살펴볼 구간이 한 칸이라도 남아 있는 동안만 계속한다는 뜻입니다. 범위를 줄이다 low가 high를 넘어서면 후보가 하나도 없으므로 값이 목록에 없다고 판단합니다. 원문이 강조하듯 이 판단은 목록이 정렬되어 있을 때만 성립합니다.

핵심 정리

• 정렬되지 않은 목록에서는 버린 절반에 값이 있을 수 있습니다.

본문 근거: S1 · 원문 줄: 19–20 · 설정 모델: 없음 — 직접 작성한 예시 · 생성: 2026-10-22T00:00:00.000Z

3 호출 예시로 결과 예상하기

원문 코드

scores = [2, 5, 8, 12, 16]
print(binary_search(scores, 12))
print(binary_search(scores, 7))

scores는 오름차순으로 정렬된 목록입니다. 12는 네 번째 원소이므로 위치 3을 찾고, 7은 목록에 없으므로 -1을 돌려줄 것으로 읽을 수 있습니다.

핵심 정리

• 파이썬 목록의 위치는 0부터 셉니다.

예상 동작(실행하지 않음)

첫 줄은 3, 둘째 줄은 -1을 출력할 것으로 예상합니다. 이 코드는 실행하지 않았습니다.

본문 근거: S1 · 원문 줄: 23–25 · 설정 모델: 없음 — 직접 작성한 예시 · 생성: 2026-10-22T00:00:00.000Z