二分与排序思想

def binary_search(nums: list[int], target: int) -> int:
    """闭区间模板：在有序 nums 中找 target 的下标，找不到返回 -1。"""
    lo, hi = 0, len(nums) - 1          # 不变量：答案若存在，落在闭区间 [lo, hi] 内
    while lo <= hi:                    # 闭区间非空的条件是 lo <= hi
        mid = lo + (hi - lo) // 2      # 取中点，写法避免 lo+hi 溢出（见下方警告）
        if nums[mid] == target:
            return mid                 # 命中，直接返回
        elif nums[mid] < target:
            lo = mid + 1               # target 在右半，排除 mid 及其左侧
        else:
            hi = mid - 1               # target 在左半，排除 mid 及其右侧
    return -1                          # 区间收空仍未命中


if __name__ == "__main__":
    arr = [3, 9, 14, 19, 23, 28, 37, 45]
    print(binary_search(arr, 23))      # 4
    print(binary_search(arr, 10))      # -1

def left_bound(nums: list[int], target: int) -> int:
    """在含重复元素的有序数组中，返回 target 第一次出现的下标，没有则返回 -1。"""
    lo, hi = 0, len(nums) - 1
    ans = -1                           # 候选：记录目前见过的最靠左的命中位置
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] < target:
            lo = mid + 1               # 太小，去右半
        elif nums[mid] > target:
            hi = mid - 1               # 太大，去左半
        else:                          # 命中：先记下，再继续向左找更早的命中
            ans = mid
            hi = mid - 1               # 关键：不返回，逼向左边界
    return ans


if __name__ == "__main__":
    arr = [1, 2, 2, 2, 3, 4]
    print(left_bound(arr, 2))          # 1  （第一个 2 的下标）
    print(left_bound(arr, 5))          # -1

import math


def min_eating_speed(piles: list[int], h: int) -> int:
    """对答案（速度）二分：返回 h 小时内吃完所有香蕉的最小速度。"""

    def check(speed: int) -> bool:
        # 以 speed 吃完所需总小时数；每堆向上取整（吃不满也占一小时）
        hours = sum(math.ceil(p / speed) for p in piles)
        return hours <= h          # 可行 = 能在 h 小时内吃完

    lo, hi = 1, max(piles)          # 答案空间：速度至少 1，至多 max（一小时一堆）
    ans = hi                        # 候选：hi 一定可行（每堆一小时吃完）
    while lo <= hi:                 # 闭区间二分，但比较换成 check
        mid = lo + (hi - lo) // 2
        if check(mid):             # mid 可行 ⇒ 记录，并尝试更小的速度
            ans = mid
            hi = mid - 1
        else:                      # mid 不可行 ⇒ 速度必须更大
            lo = mid + 1
    return ans


if __name__ == "__main__":
    print(min_eating_speed([3, 6, 7, 11], 8))        # 4
    print(min_eating_speed([30, 11, 23, 4, 20], 5))  # 30
    print(min_eating_speed([30, 11, 23, 4, 20], 6))  # 23

def three_sum(nums: list[int]) -> list[list[int]]:
    """返回所有和为 0 的不重复三元组。排序 O(n log n) + 对撞双指针 O(n^2)。"""
    nums.sort()                        # 预处理：排序，使双指针与去重都成为可能
    n = len(nums)
    res: list[list[int]] = []
    for i in range(n - 2):
        if nums[i] > 0:                # 已排序，最小数 > 0 则三数之和不可能为 0
            break
        if i > 0 and nums[i] == nums[i - 1]:
            continue                   # 跳过重复的第一个数，避免重复三元组
        lo, hi = i + 1, n - 1          # 对撞双指针：在右侧有序区间找两数之和
        while lo < hi:
            s = nums[i] + nums[lo] + nums[hi]
            if s < 0:
                lo += 1                # 和偏小，左指针右移增大
            elif s > 0:
                hi -= 1                # 和偏大，右指针左移减小
            else:
                res.append([nums[i], nums[lo], nums[hi]])
                lo += 1
                hi -= 1
                while lo < hi and nums[lo] == nums[lo - 1]:
                    lo += 1            # 跳过重复的第二个数
                while lo < hi and nums[hi] == nums[hi + 1]:
                    hi -= 1            # 跳过重复的第三个数
    return res


if __name__ == "__main__":
    print(three_sum([-1, 0, 1, 2, -1, -4]))   # [[-1, -1, 2], [-1, 0, 1]]
    print(three_sum([0, 0, 0, 0]))            # [[0, 0, 0]]