정렬된 배열에서 가운데 값을 보고, 찾는 값이 왼쪽 절반에 있는지 오른쪽 절반에 있는지 판단해 후보를 매번 절반으로 줄입니다.

이분 탐색에서 lo, mid, hi가 움직이며 후보가 줄어드는 과정을 보여 주는 시뮬레이터

찾는 값을 바꾸거나 [배열 안의 값 고르기]를 누른 뒤 재생하세요. 흐려진 칸은 이미 후보에서 버린 칸입니다.

시간O(log n)

조건정렬된 배열

100만 개최대 20번

10억 개최대 30번

세 가지 형태

값 찾기는 같은 값을 만나면 바로 끝냅니다. lower bound는 x 이상인 값이 처음 나오는 위치를, upper bound는 x를 초과하는 값이 처음 나오는 위치를 돌려줍니다. upper bound − lower bound가 배열 안의 x의 개수입니다. [같은 값 많음]에서 두 버튼을 번갈아 실행해 보세요. 파이썬에서는 bisect_left(a, x)가 lower bound, bisect_right(a, x)가 upper bound입니다.

경계 조건을 하나로 정하세요

값 찾기는 닫힌 구간 [lo, hi]와 lo <= hi를, lower/upper bound는 반열린 구간 [lo, hi)와 lo < hi를 씁니다. 한 코드 안에서 두 방식을 섞으면 무한 루프에 빠지거나 답이 한 칸 어긋납니다.

코테에서는: 답을 이분 탐색하는 파라메트릭 서치

"조건을 만족하는 가장 큰(작은) 값"을 묻는 문제는, 답을 x로 정했을 때 조건을 만족하는지 판정하는 문제로 바꿉니다. x를 키워 가면 판정 결과가 참 참 참 거짓 거짓처럼 한 번만 바뀌므로, 그 경계를 이분 탐색으로 찾습니다. 랜선 자르기, 나무 자르기, 공유기 설치가 대표적인 유형입니다.

lo, hi = 1, max(a)          # 답이 될 수 있는 범위
while lo <= hi:
    mid = (lo + hi) // 2
    if ok(mid):             # mid로 조건을 만족하면
        ans = mid
        lo = mid + 1        # 더 큰 답을 시도
    else:
        hi = mid - 1