Бинарный поиск по ответу

Бинарный поиск по ответу применяется, когда сам ответ — это число из диапазона, а свойство «подходит / не подходит» монотонно. Мы бинарно ищем границу, на каждом шаге вызывая проверочную функцию can(x).

Сложность: время O(n · log R), где R — длина диапазона ответов, n — стоимость одной проверки. Память: O(1). Пример: минимальная скорость, минимальная вместимость, «делим массив на k частей».

def min_capacity(weights, days):
    def can(cap):
        d, cur = 1, 0
        for w in weights:
            if cur + w > cap:
                d += 1
                cur = 0
            cur += w
        return d <= days
    lo, hi = max(weights), sum(weights)
    while lo < hi:
        mid = (lo + hi) // 2
        if can(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo