---
title: "이진 탐색: 답이 있는 구간을 매번 절반으로 줄이기"
author: "Lee"
published_at: "2026-10-28T12:58:02.000Z"
updated_at: "2026-09-30T09:38:47.278Z"
tags: ["컴퓨터공학","알고리즘"]
canonical_url: "https://ariser.io/@writer_a1cd615ab19e/%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-%EB%8B%B5%EC%9D%B4-%EC%9E%88%EB%8A%94-%EA%B5%AC%EA%B0%84%EC%9D%84-%EB%A7%A4%EB%B2%88-%EC%A0%88%EB%B0%98%EC%9C%BC%EB%A1%9C-%EC%A4%84%EC%9D%B4%EA%B8%B0"
ai_assisted: false
---

# 이진 탐색: 답이 있는 구간을 매번 절반으로 줄이기

[원문](https://ariser.io/@writer_a1cd615ab19e/%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-%EB%8B%B5%EC%9D%B4-%EC%9E%88%EB%8A%94-%EA%B5%AC%EA%B0%84%EC%9D%84-%EB%A7%A4%EB%B2%88-%EC%A0%88%EB%B0%98%EC%9C%BC%EB%A1%9C-%EC%A4%84%EC%9D%B4%EA%B8%B0)

이진 탐색은 비교 결과에 따라 후보 구간의 절반을 버리는 방법이다. 정렬 배열 검색으로 알려져 있지만 본질은 조건이 한 방향으로만 변하는 단조성이다. 조건이 false인 구간 뒤에 true인 구간이 이어지면 최초 true 위치를 찾을 수 있다.

![정렬된 배열에서 중간값 7을 비교한 뒤 중간값 11을 찾아내는 이진 탐색](/api/v1/media/db5522c5-d24e-4bfe-9d70-6b415af6a903)

*비교 결과에 따라 정답이 있을 수 있는 구간만 남긴다.*

### 구간의 뜻을 고정한다

아래 lower_bound는 정렬된 배열에서 target 이상인 첫 위치를 반환한다. 탐색 범위를 반열린 구간 [left,right)로 정하고, 답이 배열 끝일 수도 있어 초기 right를 n으로 둔다.

```python
def lower_bound(sorted_values, target):
    left = 0
    right = len(sorted_values)
    while left < right:
        middle = left + (right - left) // 2
        if sorted_values[middle] < target:
            left = middle + 1
        else:
            right = middle
    return left

def contains(sorted_values, target):
    position = lower_bound(sorted_values, target)
    return position < len(sorted_values) and sorted_values[position] == target
```

left보다 앞의 값은 target보다 작다고 이미 확인했고, right 이상은 답의 후보 경계 바깥이다. middle 값이 작으면 middle까지 제외해 left=middle+1, 크거나 같으면 middle 자체가 답일 수 있어 right=middle로 둔다. 이 불변식이 경계 처리를 설명한다.

### 중복과 없는 값도 처리하기

[1,3,3,7,9]에서 target=3이면 최초 위치 1을 얻는다. target=6이면 위치 3이 나오지만 값은 7이므로 실제 존재하지 않는다. target=10이면 n이 반환된다. 위치를 얻은 뒤 배열에 접근하기 전에 범위를 검사해야 한다.

각 단계에서 후보 길이가 대략 절반이 되어 비교 횟수는 O(log n), 반복 구현의 추가 공간은 O(1)이다. n개 데이터를 먼저 정렬해야 한다면 그 비용을 따로 더해야 하며 한 번의 조회만 한다면 선형 탐색보다 유리하지 않을 수도 있다.

폐구간 [left,right] 구현도 가능하지만 종료 조건과 갱신 규칙이 달라진다. 서로 다른 방식의 right 초기값, while 조건, middle 이동을 섞으면 무한 반복이나 한 칸 오류가 생긴다. 코드를 외우기보다 어느 위치가 아직 답일 수 있는지 말로 설명하는 것이 좋다.

고정 폭 정수에서는 (left+right)//2가 오버플로할 수 있어 left+(right-left)//2를 쓴다. Python 정수에는 같은 문제가 없지만 알고리즘을 다른 언어로 옮길 때 의미가 있다.

최소 용량, 최소 시간처럼 답 자체에 이진 탐색을 적용할 수도 있다. 이 경우 “용량 x에서 가능하다면 더 큰 용량에서도 가능하다” 같은 단조 조건을 먼저 증명해야 한다. 판정 함수가 O(f(n))이면 전체 비용은 탐색 단계 수에 그 판정 비용을 곱한 값이다. 단조성이 없으면 절반을 버리는 근거도 없다.

### 참고 자료

- [MIT OpenCourseWare · Introduction to Algorithms](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/)