二分法解题模板

二分法

今天重新审视了二分法，结合同事的思考认为，

二分的本质是，在一段或多段单调序列里找分界点

使用左开右闭 [l, r) 的模板如下：

def binary_search(l, r):
    while l < r:
        m = l + (r - l) // 2
        if f(m): return m # optional
        if g(m):
            r = m  # new range [l, m)
        else:
            l = m + 1 # new range [m+1, r)
    return l # or not found

m 如果满足查找条件，即 f(m) 返回 true，则查找结束。如果 f(m) 返回 false， 则根据 g(m) 的结果构造新的查找区间。如果新区间在左边，则新的左闭右开区间是 [l, m) 等价于 [l, m-1]；如果新区间在右边，则新的左闭右开是 [m+1, r)。

Return the lower_bound / upper_bound of a value x in a sorted array.

lower_bound(A, x): first index of i, such that A[i] >= x

def lower_bound(A, x, l, r):
    while l < r:
        m = (l + r) // 2
        if A[m] >= x:
            r = m
        else:
            l = m + 1
     return l

if A[m] == x, still need to update right bound to m as there are probable mutiple x at the left of m.

upper_bound(A, x): first index of i, such that A[i] > x

def upper_bound(A, x, l, r):
    while l < r:
        m = (l + r) // 2
        if A[m] > x:
            r = m
        else:
            l = m + 1
     return l

案例应用

案例 1：Capacity to Ship Packages Within D Days

https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:

        l, r = max(weights), sum(weights)

        while l < r:
            m = (l + r) // 2

            s = 0
            rounds = 1
            for i in range(len(weights)):
                if s + weights[i] <= m:
                    s += weights[i]
                else: # overload, need next round
                    s = weights[i]
                    rounds += 1

            if rounds <= D:
                r = m
            else:
                l = m + 1

        return l

案例 2：Coko Eating Bananas

https://leetcode.com/problems/koko-eating-bananas/

class Solution:
    def minEatingSpeed(self, piles: List[int], H: int) -> int:
        l, r = 1, max(piles) + 1

        while l < r:
            m = l + (r - l) // 2

            time = 0
            for x in piles:
                time += math.ceil(x / m)
            if time <= H:
                r = m
            else:
                l = m + 1

        return l