leetcode刷题记录【二分查找类题目】—Python代码+详细注释

题目：875. 爱吃香蕉的珂珂
难度：中等
算法：寻找左侧边界的⼆分查找

# 2022.05.06
class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        # 定义一个函数返回吃完香蕉的时间（ceil是math自带函数，向上取整，向下是floor）
        def cal(mid):
            sum_h = 0
            for i in piles:
                sum_h += ceil(i / mid)
            return sum_h
        # 最大速度是堆中最大的数值，最小是1，分别作为二分搜索的上下限
        right = max(piles)
        left = 1
        # 二分搜索
        while left <= right:
            mid = (left + right) // 2
            # 即使能按时吃完，也要往更小的速度找一下，否则不对，比如[1,1,1,999999999]，输出了156250000，其实结果应该是142857143，就是因为没有再更小的速度找
            if cal(mid) == h:
                right = mid - 1
            elif cal(mid) < h:
                right = mid - 1
            elif cal(mid) > h:
                left = mid + 1
        # 返回left或者right + 1
        return left

题目：1011. 在 D 天内送达包裹的能力
难度：中等
算法：寻找左侧边界的⼆分查找

# 2022.05.08
class Solution:
    def shipWithinDays(self, weights: List[int], days: int) -> int:
        def cal(mid): 
            # 写法一：复杂度有点高
            # i = 0
            # cnt_day = 0
            # while i < len(weights):
            #     print(i)
            #     sum_tmp = 0
            #     while i < len(weights) and sum_tmp + weights[i] <= mid:
            #         sum_tmp += weights[i]
            #         i += 1
            #     cnt_day += 1
            # return cnt_day

            # 写法二：最后一波不会超过mid，所以不会进入if当中的cnt_day += 1操作，因此cnt_day要从1开始计数，或者最后返回cnt_day + 1也可以
            cnt_day = 1
            curWeight = 0
            for i in weights:
                curWeight += i
                if curWeight > mid:
                    curWeight = i
                    cnt_day += 1
            return cnt_day
        # 这题最小值至少要大于包裹最大值才行
        left = max(weights)
        # 最大值为一次运完，即把所有的包裹运完
        right = sum(weights)
        while left <= right:
            mid = (left + right) // 2
            if cal(mid) == days:
                right = mid - 1
            if cal(mid) < days:
                right = mid - 1
            if cal(mid) > days:
                left = mid + 1
        return left