[이분 탐색 (Binary Search)]

the.Dev.Cat 2026. 4. 28. 17:58

이분 탐색 (Binary Search) -- 코딩테스트 스터디 7주차

코딩테스트 스터디 7주차 학습 자료를 정리한 글이다.

정렬된 배열에서 탐색 범위를 절반씩 줄여 나가는 알고리즘과, 이를 확장해 최적값을 구하는 파라메트릭 서치를 다룬다.

1. 이분 탐색 기초

이분 탐색이란

이분 탐색은 정렬된 배열에서 특정 값을 찾을 때 사용하는 탐색 알고리즘이다. 처음부터 끝까지 하나씩 확인하는 선형 탐색은 O(n)이지만, 이분 탐색은 O(log n)이다. n이 10억이어도 탐색 횟수는 30번이면 충분하다.

전화번호부를 펼칠 때와 같은 원리다. "박지훈"을 찾는다면 책 한가운데를 펼쳐서 현재 위치가 "박"보다 앞인지 뒤인지 확인한다. 앞이라면 오른쪽 절반만, 뒤라면 왼쪽 절반만 남긴다. 이 과정을 반복하면 수천 페이지의 전화번호부도 10번 남짓한 탐색으로 찾을 수 있다.

단, 이분 탐색은 반드시 정렬된 상태에서만 사용할 수 있다. 정렬되지 않은 배열에서는 "이쪽 절반에 있다"는 판단 자체가 불가능하기 때문이다.

left, right, mid 포인터 설계

이분 탐색은 세 개의 포인터로 탐색 범위를 관리한다.

left: 탐색 범위의 왼쪽 경계 (인덱스)
right: 탐색 범위의 오른쪽 경계 (인덱스)
mid: 탐색 범위의 중간 인덱스 ((left + right) // 2)

mid에 있는 값과 목표 값을 비교해서, 목표가 더 크면 left = mid + 1로 왼쪽 절반을 버리고, 목표가 더 작으면 right = mid - 1로 오른쪽 절반을 버린다.

배열: [2, 5, 8, 12, 16, 23, 38, 45]
target: 23

초기:   left=0  right=7  mid=3  arr[3]=12  12 < 23  → left=4
2단계:  left=4  right=7  mid=5  arr[5]=23  찾음!

종료 조건은 left > right다. 탐색 범위가 빌 때까지 찾지 못하면 목표 값이 배열에 없는 것이다.

off-by-one 실수 방지

이분 탐색에서 가장 자주 나오는 실수는 경계 처리다.

mid = (left + right) // 2로 중간 인덱스를 구한다.
arr[mid]가 target보다 작으면 left = mid + 1이다. mid는 이미 확인했으므로 포함하지 않는다.
arr[mid]가 target보다 크면 right = mid - 1이다. 마찬가지로 mid를 제외한다.
종료 조건은 left <= right가 참인 동안 반복한다. left < right로 쓰면 탐색 범위가 1개 남았을 때 확인하지 못하고 빠져나온다.

기본 구현: target 찾기

def binary_search(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

arr = [2, 5, 8, 12, 16, 23, 38, 45]
print(binary_search(arr, 23))
print(binary_search(arr, 10))

출력:

5
-1

2. 하한과 상한

배열에 중복 값이 있거나, 정확한 값 대신 "가장 가까운 위치"를 찾아야 할 때는 하한(lower bound)과 상한(upper bound)이 필요하다.

하한(lower bound): target 이상인 값 중 가장 왼쪽 인덱스
상한(upper bound): target 초과인 값 중 가장 왼쪽 인덱스

예를 들어 [1, 3, 3, 5, 5, 5, 8]에서 target이 5라면:

lower bound: 인덱스 3 (첫 번째 5의 위치)
upper bound: 인덱스 6 (마지막 5 다음 위치, 즉 8의 위치)

배열:  [1, 3, 3, 5, 5, 5, 8]
인덱스: 0  1  2  3  4  5  6

lower_bound(5) → 3
upper_bound(5) → 6

두 값을 이용하면 5의 개수는 6 - 3 = 3으로 바로 구할 수 있다.

def lower_bound(arr, target):
    left, right = 0, len(arr)

    while left < right:
        mid = (left + right) // 2

        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid

    return left


def upper_bound(arr, target):
    left, right = 0, len(arr)

    while left < right:
        mid = (left + right) // 2

        if arr[mid] <= target:
            left = mid + 1
        else:
            right = mid

    return left

right = len(arr)로 초기화한다. target이 배열의 모든 원소보다 크다면 마지막 인덱스+1을 반환해야 하기 때문이다. 종료 조건도 left < right로 달라진다. right = mid로 범위를 줄이면서 left와 right가 같아지는 순간 탐색을 마친다.

arr = [1, 3, 3, 5, 5, 5, 8]
print(lower_bound(arr, 5))
print(upper_bound(arr, 5))
print(upper_bound(arr, 5) - lower_bound(arr, 5))

출력:

3
6
3

3. Python bisect 모듈

Python 표준 라이브러리 bisect는 lower_bound와 upper_bound를 제공한다.

bisect.bisect_left(arr, target): lower_bound와 동일
bisect.bisect_right(arr, target): upper_bound와 동일 (bisect()도 동일)

함수	반환값	설명
`bisect_left(a, x)`	왼쪽 인덱스	x 이상인 첫 번째 위치
`bisect_right(a, x)`	오른쪽 인덱스	x 초과인 첫 번째 위치
`insort_left(a, x)`	None	정렬 유지하며 왼쪽에 삽입
`insort_right(a, x)`	None	정렬 유지하며 오른쪽에 삽입

x의 개수 세기

import bisect

a = [1, 3, 3, 5, 5, 5, 8]
x = 5

count = bisect.bisect_right(a, x) - bisect.bisect_left(a, x)
print(count)

출력:

3

bisect_right(a, 5) = 6, bisect_left(a, 5) = 3이므로 5는 3개다.

x 이상인 첫 번째 값의 인덱스 찾기

import bisect

a = [2, 4, 6, 8, 10]
x = 5

idx = bisect.bisect_left(a, x)
print(idx)
print(a[idx])

출력:

2
6

bisect_left(a, 5)는 5가 삽입될 위치인 인덱스 2를 반환한다. a[2]는 6으로, 5 이상인 첫 번째 값이다. 해당 값이 존재하지 않을 수 있으므로 idx < len(a) 검사를 함께 수행한다.

insort -- 정렬 유지하며 삽입

import bisect

a = [1, 3, 5, 7]
bisect.insort_left(a, 4)
print(a)

bisect.insort_right(a, 5)
print(a)

출력:

[1, 3, 4, 5, 7]
[1, 3, 4, 5, 5, 7]

insort는 이진 탐색으로 위치를 찾지만(O(log n)), 리스트 삽입 자체는 O(n)이다. 삽입이 빈번한 경우 SortedList(sortedcontainers 패키지) 사용을 검토한다. BOJ에서는 sortedcontainers가 사용 불가하므로 insort가 표준이다.

4. 파라메트릭 서치

파라메트릭 서치란

파라메트릭 서치는 "답이 될 수 있는 값의 범위"에 이분 탐색을 적용하는 기법이다. 특정 값을 찾는 것이 아니라, 조건을 만족하는 값의 최댓값 또는 최솟값을 구하는 문제에 사용한다.

전형적인 문제 유형은 두 가지다.

최솟값의 최댓값: "조건을 만족하면서 값을 가능한 크게"
최댓값의 최솟값: "조건을 만족하면서 값을 가능한 작게"

어떤 기준값 mid에 대해 조건이 성립하는지 확인하는 함수 is_possible(mid)를 만들고, 이 함수를 기반으로 이분 탐색을 수행한다.

is_possible(mid) = True

더 큰(또는 더 작은) 값이 가능하다
탐색 범위를 유리한 방향으로 조정

is_possible(mid) = False

이 값은 불가능하다
반대 방향으로 탐색 범위를 조정

예시: 나무 자르기

N개의 나무를 절단기 높이 H로 잘랐을 때, 가져갈 수 있는 나무 합이 M 이상이 되려면 H의 최댓값은 얼마인가?

나무 높이: [20, 15, 10, 17]
M = 7

H=15: [5, 0, 0, 2] → 합 7 → 가능
H=17: [3, 0, 0, 0] → 합 3 → 불가능
H=16: [4, 0, 0, 1] → 합 5 → 불가능
H=15: 가능한 최댓값

이분 탐색 범위: [0, max(나무 높이)]

조건 함수: H로 잘랐을 때 얻을 수 있는 나무 합이 M 이상인지 확인.

def can_get(trees, h, m):
    total = sum(max(0, tree - h) for tree in trees)
    return total >= m


def max_cut_height(trees, m):
    left, right = 0, max(trees)
    answer = 0

    while left <= right:
        mid = (left + right) // 2

        if can_get(trees, mid, m):
            answer = mid
            left = mid + 1
        else:
            right = mid - 1

    return answer

trees = [20, 15, 10, 17]
m = 7
print(max_cut_height(trees, m))

출력:

15

can_get이 True면 더 크게 자를 수 있으므로 left = mid + 1로 이동한다. False면 H가 너무 높다는 뜻이므로 right = mid - 1로 줄인다. answer는 가능한 경우만 갱신하므로 루프가 끝났을 때 최댓값이 남는다.

예시: 랜선 자르기

K개의 랜선을 N개의 동일한 길이로 자르려면, 자를 수 있는 최대 길이는 얼마인가?

def max_lan_length(cables, n):
    left, right = 1, max(cables)
    answer = 0

    while left <= right:
        mid = (left + right) // 2
        count = sum(cable // mid for cable in cables)

        if count >= n:
            answer = mid
            left = mid + 1
        else:
            right = mid - 1

    return answer

cables = [802, 743, 457, 539]
n = 11
print(max_lan_length(cables, n))

출력:

200

5. 시간 복잡도 정리

연산	시간 복잡도	비고
기본 이분 탐색	O(log n)	정렬된 배열 필요
lower_bound / upper_bound	O(log n)	bisect 모듈 동일
파라메트릭 서치	O(log(범위) × f(n))	f(n): 조건 함수 시간 복잡도
정렬 후 이분 탐색	O(n log n)	정렬이 병목

6. 연습 문제

문제	난이도	링크	핵심 접근
입국심사	Lv 3	프로그래머스	파라메트릭 서치, 심사 시간 최솟값 이분 탐색
징검다리	Lv 3	프로그래머스	이분 탐색으로 제거할 돌의 최솟값 탐색
징검다리 건너기	Lv 4	프로그래머스	파라메트릭 서치, 건널 수 있는 최대 인원 이분 탐색