விடையில் Binary Search (Search on Answer)

சில நேரங்களில் index அல்ல, விடை மதிப்பு (capacity, k) binary search. தேவை: (1) answer range, (2) monotone check(x).

Try this in Python

def min_capacity(weights: list[int], days: int) -> int:
    def can(cap: int) -> bool:
        need, cur = 1, 0
        for w in weights:
            if w > cap:
                return False
            if cur + w > cap:
                need += 1
                cur = 0
            cur += w
        return need <= 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


print(min_capacity([1, 2, 3, 4, 5], 3))

Key takeaways

• check(x) செலவு கட்டுப்பாடு.
• Monotonicity நிரூபி: பொதுவாக பெரிய cap-யும் வேலை செய்யும்.
• hi upper bound-ஐ முதலில் நியாயமாகத் தேர்ந்தெடு.