第六章：二分查找

本章目标

本章学习二分查找。二分不只用于数组找数，也能用于满足单调性的答案空间。

你会掌握 left、right、mid 的边界更新，并能写出 lower bound 模板。

核心概念

标准二分要求搜索空间有序。每次比较 mid 后，至少排除一半候选，因此时间复杂度是 O(log n)。

答案空间二分要求判断函数具有单调性。例如速度越快越容易按时完成，就可以二分最小可行速度。

Python 示例

下面是 lower bound：返回第一个大于等于 target 的位置。

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

如果把 nums 换成答案范围，把比较换成可行性检查，就是二分答案空间。

复杂度与常见误区

二分查找时间复杂度是 O(log n)，额外空间通常是 O(1)。如果判断函数本身是 O(n)，答案空间二分总复杂度会变成 O(n log M)。

常见误区是混用闭区间和左闭右开区间。模板可以不同，但每次更新必须保持同一个不变量。

本章要点

看到有序数组、最大值最小化、最小值最大化、单调可行性时，要主动考虑二分查找。

写二分前先用一句话定义答案：left 最终应该停在什么位置。这样边界错误会少很多。