이진 탐색이 하는 일

정렬된 배열에서 값을 찾을 때 처음부터 하나씩 보면 길이 만큼 걸린다. 이진 탐색(binary search)은 찾는 범위의 가운데 값을 하나 보고, 답이 그보다 왼쪽에 있는지 오른쪽에 있는지 판단해 범위를 절반으로 줄인다. 범위가 매번 절반이 되므로 번 안에 끝나고, time complexity 는 이다.

이 방법이 배열에만 쓰이는 것은 아니다. 범위를 절반으로 버릴 수 있는 근거는 “가운데 값 하나를 보면 답이 어느 쪽에 있는지 알 수 있다” 는 성질뿐이다. 이 성질은 배열이 정렬돼 있을 때도 생기지만, 답의 후보가 되는 수 자체에 대해 생기기도 한다. 다음 절의 답 이진 탐색이 그런 경우다.

답 이진 탐색: 조건을 만족하는 최솟값 찾기

“하루에 바나나를 몇 개씩 먹어야 기한 안에 다 먹는가” 처럼 조건을 만족하는 값 중 가장 작은 값 을 묻는 문제가 있다. 답을 직접 계산하기는 어렵지만, 값 하나를 정해 주면 그 값이 조건을 만족하는지는 쉽게 확인할 수 있는 경우가 많다.

이럴 때 답이 될 수 있는 수의 범위를 정해 두고, 그 범위에서 이진 탐색을 한다. 배열의 원소 대신 답의 후보를 탐색한다고 해서 답 이진 탐색, 또는 parametric search 라고 부른다.

판정 결과가 한 번만 바뀌어야 한다

값 가 조건을 만족하는지 참·거짓으로 돌려주는 함수를 판정 함수 라고 하자. 답 이진 탐색이 성립하려면 판정 결과가 를 키우는 동안 거짓에서 참으로 한 번만 바뀌어야 한다.

x      :  1   2   3   4   5   6   7
ok(x)  :  F   F   F   T   T   T   T
                      ↑
                      답 = 처음으로 T 가 되는 x

바나나를 하루에 4 개씩 먹어서 기한을 맞출 수 있으면 5 개씩 먹어도 맞출 수 있다. 이렇게 “어떤 값이 되면 그보다 큰 값도 모두 된다” 는 성질이 있으면 판정 결과가 위 그림처럼 한 번만 바뀐다. 가운데 하나를 판정해서 T 가 나오면 답은 그 자리이거나 왼쪽에 있고, F 가 나오면 답은 오른쪽에 있다. 그래서 범위를 절반씩 버릴 수 있다.

틀

lo, hi = 답이 될 수 있는 가장 작은 값, 답이 될 수 있는 가장 큰 값
while lo < hi:
    mid = (lo + hi) // 2
    if ok(mid):
        hi = mid        # mid 도 답일 수 있으므로 남긴다
    else:
        lo = mid + 1    # mid 는 답이 아니므로 버린다
return lo

hi 는 판정이 반드시 참인 값으로 잡는다. 그래야 범위 안에 답이 적어도 하나 있다.

끝나면 lo 가 답인 이유

이 틀은 반복 내내 답이 [lo, hi] 안에 있다 는 상태를 지킨다. 처음에는 lo 와 hi 를 답이 될 수 있는 범위의 양 끝으로 잡았으므로 성립한다. 반복 한 번이 이 상태를 깨지 않는지 두 경우로 나눠 본다.

  • ok(mid) 가 참이면, 답은 mid 이거나 그보다 작다. 그래서 hi = mid 로 오른쪽을 버린다. mid 자체가 답일 수 있으므로 mid - 1 이 아니라 mid 까지 남긴다.
  • ok(mid) 가 거짓이면, mid 와 그보다 작은 값은 모두 답이 아니다. 그래서 lo = mid + 1 로 mid 까지 버린다.

mid 는 답의 후보로 따로 저장해 두는 값이 아니라, 범위를 어느 쪽으로 줄일지 정하려고 찔러 보는 값이다. 답은 언제나 [lo, hi] 안에 있으므로, 반복이 끝나 lo == hi 가 되면 범위에 남은 값 하나가 답이다. 그래서 ans = mid 같은 변수 없이 lo 를 그대로 반환한다.

mid 를 내림해야 반복이 끝난다

lo < hi 이면 mid = (lo + hi) // 2 는 lo 이상, hi 미만이다. 그래서 hi = mid 는 hi 를 적어도 1 줄이고, lo = mid + 1 은 lo 를 적어도 1 늘린다. 어느 쪽이든 범위가 줄어들므로 반복이 반드시 끝난다.

mid 를 올림((lo + hi + 1) // 2)으로 잡으면 lo = 4, hi = 5 에서 mid = 5 가 되고, 판정이 참이면 hi = mid = 5 로 범위가 그대로라 반복이 끝나지 않는다. 올림은 “조건을 만족하는 최댓값” 을 찾느라 lo = mid 로 갱신하는 반대쪽 틀에서 쓴다. 다음 절처럼 최댓값을 찾는 문제를 최솟값 찾기로 바꾸면 이 반대쪽 틀이 필요 없다.

조건을 만족하는 최댓값: 첫 거짓을 찾고 한 칸 앞으로

“정렬된 배열에서 이하인 값 중 마지막” 처럼 조건을 만족하는 값 중 가장 큰 값 을 묻는 문제도 있다. 이때는 판정 결과가 앞의 최솟값 문제와 반대로, 를 키우는 동안 참에서 거짓으로 한 번 바뀐다.

x      :  1   2   3   4   5   6   7
ok(x)  :  T   T   T   T   F   F   F
                      ↑   ↑
            마지막 참 = 4   5 = 첫 거짓

마지막 참과 첫 거짓은 항상 붙어 있다. 그래서 마지막 참을 직접 찾는 대신, “거짓이 되는 가장 작은 ” 를 앞의 최솟값 틀로 찾고 한 칸 앞으로 물러난다. 최솟값 틀의 판정 자리에 not ok(mid) 를 넣은 것과 같다.

lo, hi = 답이 될 수 있는 가장 작은 값, 답이 될 수 있는 가장 큰 값 + 1
while lo < hi:
    mid = (lo + hi) // 2
    if ok(mid):
        lo = mid + 1    # mid 는 참이므로 첫 거짓이 아니다
    else:
        hi = mid        # mid 가 첫 거짓일 수 있으므로 남긴다
return lo - 1           # 첫 거짓의 한 칸 앞이 마지막 참
  • hi 를 가장 큰 후보보다 하나 크게 잡는 이유는, 모든 후보가 참이면 범위 안에 첫 거짓이 없기 때문이다. 범위 끝 바로 뒤를 “거짓인 자리” 로 쳐 두면 최솟값 틀의 “hi 는 판정이 반드시 맞는 값” 이라는 조건이 지켜진다. hi 자리에서 ok 를 부르는 일은 없다. mid 는 항상 hi 보다 작기 때문이다.
  • 끝났을 때 lo - 1 이 가장 작은 후보보다 작으면 조건을 만족하는 값이 하나도 없다는 뜻이다.
  • mid 는 최솟값 틀과 같이 내림이므로 반복이 반드시 끝난다.

Python 의 bisect.bisect_right(a, t) 는 정렬된 배열 a 에서 ” 보다 큰 첫 위치” 를 돌려준다. 즉 ” 이하인가” 의 첫 거짓이고, 여기서 1 을 빼면 이하인 마지막 위치다. 이 방법을 그대로 쓰는 문제가 Time Based Key-Value Store 다. 따라가 보기와 마지막 참을 직접 찾으면 생기는 문제도 그 노트에 있다.

예제: Koko Eating Bananas

LeetCode 875. Koko Eating Bananas. 바나나 더미의 크기 목록 piles 와 기한 h 시간이 주어진다. 한 시간에 바나나를 최대 k 개 먹을 수 있고, 한 시간에는 더미 하나만 먹는다. 더미에 k 개보다 적게 남았으면 그 더미를 다 먹고 남은 시간은 쉰다. h 시간 안에 다 먹을 수 있는 가장 작은 k 를 구한다.

판정 함수

속도 k 로 더미 하나를 다 먹는 데 걸리는 시간은 더미 크기를 k 로 나눠 올림한 값이다. 전체 시간은 이것을 모든 더미에 대해 더한 것이다.

기호뜻
번째 더미의 바나나 개수
더미의 개수
한 시간에 먹는 바나나 개수 (구할 값)
속도 로 모든 더미를 먹는 데 걸리는 시간

판정 함수는 이다. 를 키우면 더미마다 걸리는 시간이 같거나 줄어드므로 도 같거나 줄어든다. 그래서 판정 결과가 거짓에서 참으로 한 번만 바뀐다.

범위는 lo = 1, hi = max(piles) 다. k = max(piles) 이면 모든 더미를 한 시간씩에 먹으므로 이고, 문제는 를 보장하므로 hi 는 판정이 반드시 참이다. k 를 이보다 키워도 더미당 한 시간보다 줄지 않으므로 더 볼 필요가 없다.

class Solution:
    def minEatingSpeed(self, piles: list[int], h: int) -> int:
        def ok(k):
            return sum((p + k - 1) // k for p in piles) <= h
 
        lo, hi = 1, max(piles)
        while lo < hi:
            mid = (lo + hi) // 2
            if ok(mid):
                hi = mid
            else:
                lo = mid + 1
        return lo

(p + k - 1) // k 는 p / k 를 올림한 정수다. 부동소수점 math.ceil(p / k) 를 쓰지 않아도 된다.

따라가 보기

piles = [3, 6, 7, 11], h = 8 이면 답은 4 다.

lohimid판정갱신
11161 + 1 + 2 + 2 = 6참hi = 6
1631 + 2 + 3 + 4 = 10거짓lo = 4
4651 + 2 + 2 + 3 = 8참hi = 5
4541 + 2 + 2 + 3 = 8참hi = 4

lo = hi = 4 가 되어 반복이 끝난다. 마지막 줄에서 mid = 4 가 참이었지만 그 값을 따로 저장하지 않았다. hi 가 4 로 줄면서 범위 [4, 4] 에 남았기 때문이다.

판정 한 번에 더미 개를 보고, 판정은 번 한다. 전체는 다.

예제: Capacity To Ship Packages Within D Days

LeetCode 1011. Capacity To Ship Packages Within D Days. 화물 무게 목록 weights 를 주어진 순서대로 배에 싣는다. 배는 하루에 한 번 출발하고, 하루에 싣는 무게의 합은 배의 적재량을 넘을 수 없다. 화물 순서는 바꿀 수 없다. days 일 안에 모두 보낼 수 있는 가장 작은 적재량을 구한다.

판정 함수

적재량 cap 이 정해지면, 화물을 앞에서부터 실을 수 있는 만큼 싣고 다음 화물이 넘치면 다음 날로 넘기는 것이 가장 적은 날수를 쓴다. 오늘 더 실을 수 있는 화물을 내일로 미뤄서 날수가 줄어드는 일은 없기 때문이다.

def ok(cap):
    need, load = 1, 0          # 필요한 날수, 오늘 실은 무게
    for w in weights:
        if load + w > cap:     # 오늘은 더 못 싣는다
            need += 1
            load = 0
        load += w
    return need <= days

범위는 lo = max(weights), hi = sum(weights) 다. hi 는 모든 화물을 하루에 싣는 적재량이라 판정이 반드시 참이다.

lo = max(weights) 는 판정 함수가 기대는 전제다

lo 를 875 처럼 1 로 잡아도 될 것 같지만, 그러면 틀린 답이 나온다. weights = [1, 2, 3, 1, 1], days = 4 의 답은 3 인데, lo = 1 로 시작하면 2 를 돌려준다.

원인은 판정 함수가 “어떤 화물이든 빈 배에는 실린다” 고 가정한다는 데 있다. 넘칠 때 다음 날로 넘기기만 할 뿐, 넘긴 화물이 빈 배에 들어가는지는 확인하지 않는다. cap = 2 로 위 예를 따라가면 다음과 같다.

1일차: [1]      다음 화물 2 를 더하면 3 > 2 → 다음 날로
2일차: [2]      다음 화물 3 을 더하면 5 > 2 → 다음 날로
3일차: [3]      무게 3 이 적재량 2 를 넘지만 확인하지 않는다
4일차: [1, 1]

4일이 나와서 ok(2) 가 참이 된다. 실제로는 무게 3 인 화물을 실을 수 없으므로 거짓이어야 한다.

lo = max(weights) 로 시작하면 판정 함수는 cap ≥ max(weights) 인 값으로만 불린다. 이 범위에서는 모든 화물이 빈 배에 들어가므로 판정 함수의 가정이 항상 맞는다. 즉 lo 는 탐색 범위를 줄이려는 최적화가 아니라 판정 함수가 올바르게 동작하기 위한 조건이다. 판정 함수 안에 if w > cap: return False 를 넣어도 같은 문제를 막을 수 있다.

875 에서 lo = 1 이 괜찮았던 이유도 같은 기준으로 설명된다. 올림 나눗셈은 어떤 k ≥ 1 에 대해서도 더미를 다 먹는 시간을 올바르게 계산하므로, 판정 함수가 기대는 전제가 따로 없다.

코드와 따라가 보기

class Solution:
    def shipWithinDays(self, weights: list[int], days: int) -> int:
        def ok(cap):
            need, load = 1, 0
            for w in weights:
                if load + w > cap:
                    need += 1
                    load = 0
                load += w
            return need <= days
 
        lo, hi = max(weights), sum(weights)
        while lo < hi:
            mid = (lo + hi) // 2
            if ok(mid):
                hi = mid
            else:
                lo = mid + 1
        return lo

weights = [1, 2, ..., 10], days = 5 이면 답은 15 다.

lohimid판정갱신
105532참hi = 32
103221참hi = 21
102115참hi = 15
101512거짓lo = 13
131514거짓lo = 15

적재량 15 이면 [1, 2, 3, 4, 5], [6, 7], [8], [9], [10] 으로 5일이 걸린다. 14 이면 [1, 2, 3, 4] 부터 시작해 6일이 걸린다.

판정 한 번에 화물 개를 보고, 판정은 번 정도 한다. 전체는 다.

예제: Find Minimum in Rotated Sorted Array

LeetCode 153. 오름차순으로 정렬된 배열을 어느 지점에서 잘라 앞뒤를 바꿔 붙였다. 중복 값은 없다. 최솟값을 에 찾는다.

원래    : [0, 1, 2, 4, 5, 6, 7]
회전 후 : [4, 5, 6, 7, 0, 1, 2]

배열이 정렬돼 있지 않은데도 이진 탐색이 된다. 각 칸에 “이 값이 배열의 마지막 값보다 큰가?” 를 물으면 판정이 한 번만 바뀌기 때문이다.

값              :  4   5   6   7   0   1   2
nums[i] > 마지막 :  T   T   T   T   F   F   F
                               ↑
                          첫 거짓 = 최솟값

잘린 지점 앞쪽은 전부 마지막 값보다 크고, 최솟값부터 끝까지는 전부 마지막 값 이하다. 그래서 첫 거짓이 곧 최솟값이고, 앞의 최솟값 틀을 그대로 쓴다.

class Solution:
    def findMin(self, nums: list[int]) -> int:
        lo, hi = 0, len(nums) - 1
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] > nums[-1]:
                lo = mid + 1    # 잘린 지점 앞쪽, 최솟값은 mid 뒤에 있다
            else:
                hi = mid        # mid 가 최솟값일 수 있다
        return nums[lo]
  • 마지막 칸은 nums[-1] > nums[-1] 이 거짓이라 항상 거짓 쪽이다. 그래서 hi 를 len(nums) - 1 로 시작해도 첫 거짓이 범위 밖으로 나가지 않는다.
  • nums[0] 과 비교하면 안 된다. 회전하지 않은 배열 [1, 2, 3] 에서는 모든 칸이 “첫 값 이상” 이라 판정이 갈리지 않는다. 마지막 값은 회전 여부와 관계없이 항상 최솟값 쪽 구간에 속하므로 기준으로 안정적이다. 회전하지 않은 배열은 모든 칸이 거짓이 되어 첫 칸이 답으로 나온다.
  • 중복이 있는 LeetCode 154 에서는 nums[mid] == nums[-1] 이면 어느 쪽인지 알 수 없다. 이때는 hi 를 한 칸만 줄이므로 최악의 경우 이 된다.

정렬이 아니라 판정이 단조로우면 된다

이진 탐색에 필요한 것은 배열이 정렬돼 있다는 사실이 아니라, 참과 거짓을 한쪽씩 몰리게 나누는 질문 하나다. 이 노트의 예제를 나란히 놓으면 이렇다.

문제탐색 대상참과 거짓을 가르는 질문답
875먹는 속도 (숫자 범위)이 속도로 h 시간 안에 다 먹는가?첫 참
1011배 적재량 (숫자 범위)이 적재량으로 days 일 안에 다 보내는가?첫 참
Time Based Key-Value Store정렬된 timestamp이 시각이 t 이하인가?마지막 참 (첫 거짓의 한 칸 앞)
153회전된 배열이 값이 마지막 값보다 큰가?첫 거짓

875 와 1011 은 배열이 아니라 숫자 범위를 탐색하고, 153 은 정렬이 깨진 배열을 탐색한다. 처음 보는 문제에서 이진 탐색을 떠올리려면 “정렬돼 있나?” 보다 “답을 기준으로 한쪽은 전부 참, 반대쪽은 전부 거짓이 되는 질문이 있나?” 를 묻는 편이 낫다.

자주 하는 실수

  • 범위 없이 탐색하기. 후보를 절반으로 줄였다가 두 배로 늘리는 식으로 오가면, 볼 수 있는 값이 처음 값을 2 로 나눈 수들로 한정되어 답을 건너뛴다. 같은 값을 오가며 끝나지 않거나 0 으로 나누는 문제도 생긴다. 이진 탐색은 항상 [lo, hi] 범위를 들고 그 범위를 절반으로 줄인다.
  • 판정 함수 안의 올림. “바나나 p 개를 속도 k 로 먹는 시간” 을 p // k + 1 로 쓰면 나누어떨어질 때 1 이 크다. 올림은 (p + k - 1) // k 다.
  • 단위가 섞인 변수 이름. 속도를 hour 라는 이름에 담으면, 나중에 속도와 시간을 비교하는 코드를 써도 눈치채기 어렵다. speed, hours 처럼 단위가 드러나게 짓는다.
  • 내림한 mid 에 lo = mid, 그리고 열린 hi 에 hi = mid - 1. 각각 무한 루프 (B.4) 와 답 누락을 만든다. 따라가 보기는 Time Based Key-Value Store 의 C.2 에 있다.
  • 끝나고 mid 를 반환하기. 마지막으로 확인한 mid 는 거짓일 수 있다. 답은 범위가 한 칸으로 줄어든 자리인 lo 다 (B.3).

References