二分查找模板与变体

基础模板：精确查找

在升序无重复数组中找 target，经典闭区间写法：

def binary_search(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

mid = left + (right - left) // 2 防止 (left+right) 溢出（语言层面）；语义是取中点。复杂度 O(log n)，空间 O(1)。

边界二分：lower / upper bound

有重复元素或需要「第一个/最后一个」位置时，不要找到就 return，而是收缩边界：

• 第一个 >= target（lower_bound）
• 第一个 > target（即最后一个 <= 的下一个）
• 最后一个 <= target

def lower_bound(nums, target):
    left, right = 0, len(nums)  # 半开区间 [0, n)
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid
    return left  # 若 left==n 说明不存在

面试常考：搜索旋转排序数组、找峰值、平方根整数部分，本质都是判定函数 monotonic + 边界二分。

答案二分（对值二分）

当题目问「最小速度」「最大容量」「第 k 小差值」且直接枚举太慢时，在答案范围 [lo, hi] 上二分，写 check(mid) 判断是否可行：

def min_days(piles, h):
    def enough(speed):
        days = 0
        for p in piles:
            days += (p + speed - 1) // speed
        return days <= h
lo, hi = 1, max(piles)
    while lo < hi:
        mid = (lo + hi) // 2
        if enough(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

套路：1）确定 lo/hi；2）证明若 mid 可行则更大也可行（或反之）；3）二分最小可行或最大可行。

常见错误与检查清单

• 死循环：right = mid 时必须用 left + (right-left)//2 的上取中；left = mid + 1 配对 right = mid - 1 要一致。
• 区间定义：全程坚持半开或全闭，不要混用。
• 返回值：区分「不存在」与「应插入位置」；旋转数组要比较 nums[mid] 与 nums[left] 判断哪段有序。

练题建议：34、35、33、153、875、1011。掌握两套模板（边界 + 答案二分）可覆盖大部分二分标签题。