二分查找：简单到出错

第二十二章：二分查找 — 简单到出错

"我可以向你保证，90% 的计算机科学家不能在两小时内写出正确的二分查找。" — Jon Bentley，《Programming Pearls》

这句话不是危言耸听。二分查找的思想小学生都能理解：每次把搜索范围缩小一半。但把它写成代码，让它在所有边界情况下都正确——这件事从 1946 年被首次提出，到 1962 年才有人发表第一个无 bug 的实现。中间整整 16 年，无数聪明人栽在 off-by-one 错误上。

更离谱的是，2006 年 Joshua Bloch（Java 核心库作者）发现 Java 标准库中使用了 20 年的二分查找有一个整数溢出 bug。这个 bug 当初连 Jon Bentley 本人的代码里都有。

本章会把二分查找拆到骨头里。你会真正理解为什么它这么容易写错，以及如何用一套统一的框架写出永远不会错的二分查找。

Level 1 · 你需要知道的

1.1 最基本的二分查找

问题：给定一个升序排列的数组 nums 和一个目标值 target，如果 target 在数组中则返回其索引，否则返回 -1。

def binary_search(nums: list[int], target: int) -> int:
    lo, hi = 0, len(nums) - 1  # 左闭右闭 [lo, hi]
    while lo <= hi:
        mid = lo + (hi - lo) // 2  # 防止整数溢出
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

这段代码只有 10 行，但每一行都是精确的：

1. 初始化：lo = 0, hi = len(nums) - 1。搜索区间是 [lo, hi]，两端都包含。
2. 循环条件：while lo <= hi。当 lo > hi 时，搜索区间为空，退出。
3. 中点计算：mid = lo + (hi - lo) // 2。向下取整，保证 mid 不会溢出。
4. 缩小区间：找到了就返回；比 target 小就去右半边 [mid+1, hi]；比 target 大就去左半边 [lo, mid-1]。

复杂度：时间 O(log n)，空间 O(1)。每次循环区间缩小一半，n 个元素最多比较 ⌊log₂n⌋ + 1 次。

1.2 两种写法：左闭右开 vs 左闭右闭

二分查找有两种主流写法，区别在于如何定义搜索区间。

写法一：左闭右闭 [lo, hi]

def search_closed(nums: list[int], target: int) -> int:
    lo, hi = 0, len(nums) - 1
    while lo <= hi:             # 区间非空的条件
        mid = lo + (hi - lo) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            lo = mid + 1        # mid 已排除，左边界右移
        else:
            hi = mid - 1        # mid 已排除，右边界左移
    return -1

写法二：左闭右开 [lo, hi)

def search_half_open(nums: list[int], target: int) -> int:
    lo, hi = 0, len(nums)      # 注意 hi = len(nums)
    while lo < hi:              # 区间非空的条件变了
        mid = lo + (hi - lo) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            lo = mid + 1        # mid 已排除
        else:
            hi = mid            # 注意！不是 mid - 1
    return -1

关键区别对比：

哪种更好？ 没有绝对答案。但左闭右开在处理"查找第一个满足条件的位置"时更自然，因为退出时 lo == hi 就是答案。Python 的 bisect 模块用的就是左闭右开。本章后续会两种都用，你需要两种都掌握。

1.3 bisect 模块

Python 标准库的 bisect 模块提供了高效的二分查找工具：

import bisect

# bisect_left: 找到 target 应该插入的最左位置
# 等价于：第一个 >= target 的位置
pos = bisect.bisect_left([1, 3, 5, 7, 9], 5)   # 返回 2

# bisect_right (也叫 bisect): 找到 target 应该插入的最右位置
# 等价于：第一个 > target 的位置
pos = bisect.bisect_right([1, 3, 5, 7, 9], 5)  # 返回 3

# insort_left: 插入并保持排序
a = [1, 3, 5, 7, 9]
bisect.insort_left(a, 5)   # a = [1, 3, 5, 5, 7, 9]

# insort_right: 插入到相等元素的右边
a = [1, 3, 5, 7, 9]
bisect.insort_right(a, 5)  # a = [1, 3, 5, 5, 7, 9]，但 5 在原来的 5 右边

bisect_left 和 bisect_right 的区别：

当数组中存在多个等于 target 的元素时：

• bisect_left 返回最左边那个的索引（第一个 >= target 的位置）
• bisect_right 返回最右边那个的下一个索引（第一个 > target 的位置）

arr = [1, 3, 5, 5, 5, 7, 9]
bisect.bisect_left(arr, 5)   # 2 (第一个 5 的位置)
bisect.bisect_right(arr, 5)  # 5 (最后一个 5 的下一个位置)

用 bisect 实现精确查找：

def binary_search_bisect(nums: list[int], target: int) -> int:
    i = bisect.bisect_left(nums, target)
    if i < len(nums) and nums[i] == target:
        return i
    return -1

1.4 常见变体

二分查找最实用的不是"找到精确值"，而是以下四个变体：

变体 1：查找第一个 >= target 的位置（下界）

这就是 bisect_left 做的事。

def lower_bound(nums: list[int], target: int) -> int:
    """返回第一个 >= target 的索引，不存在则返回 len(nums)"""
    lo, hi = 0, len(nums)  # [lo, hi)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo

变体 2：查找第一个 > target 的位置（上界）

这就是 bisect_right 做的事。

def upper_bound(nums: list[int], target: int) -> int:
    """返回第一个 > target 的索引，不存在则返回 len(nums)"""
    lo, hi = 0, len(nums)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] <= target:  # 注意：<= 而不是 <
            lo = mid + 1
        else:
            hi = mid
    return lo

变体 3：查找最后一个 <= target 的位置

def last_le(nums: list[int], target: int) -> int:
    """返回最后一个 <= target 的索引，不存在则返回 -1"""
    return upper_bound(nums, target) - 1

变体 4：查找最后一个 < target 的位置

def last_lt(nums: list[int], target: int) -> int:
    """返回最后一个 < target 的索引，不存在则返回 -1"""
    return lower_bound(nums, target) - 1

记忆技巧：所有变体都可以用 lower_bound 和 upper_bound 组合出来：

1.5 旋转排序数组搜索

问题：一个排序数组在某个点被旋转了（如 [4,5,6,7,0,1,2]），在其中搜索 target。

关键观察：将数组从中间切开，至少有一半是有序的。

def search_rotated(nums: list[int], target: int) -> int:
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] == target:
            return mid
        
        # 判断哪一半是有序的
        if nums[lo] <= nums[mid]:
            # 左半段有序
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:
            # 右半段有序
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

逻辑分析：

1. 如果 nums[lo] <= nums[mid]，说明 [lo, mid] 是有序的。
2. 既然左半段有序，如果 target 落在 [nums[lo], nums[mid]) 范围内，就在左半段找；否则去右半段。
3. 反过来，如果右半段有序，用同样的逻辑。

Level 2 · 原理与实践

2.1 为什么二分查找这么容易写错

Jon Bentley 在《Programming Pearls》第一章就用二分查找当开场：他在贝尔实验室让高级程序员当场写二分查找，90% 的人写的代码有 bug。

常见的错误类型：

错误 1：循环条件写错

# 错误：用 [lo, hi] 但循环条件写成 lo < hi
lo, hi = 0, len(nums) - 1
while lo < hi:  # BUG! 当 lo == hi 时还有一个元素没检查
    ...

错误 2：边界更新写错

# 错误：用 [lo, hi) 但右边界更新写成 hi = mid - 1
lo, hi = 0, len(nums)
while lo < hi:
    mid = lo + (hi - lo) // 2
    if nums[mid] > target:
        hi = mid - 1  # BUG! 应该是 hi = mid
    ...

错误 3：死循环

# 错误：当 lo + 1 == hi 时，mid = lo，然后 lo = mid 不改变任何东西
lo, hi = 0, len(nums) - 1
while lo < hi:
    mid = lo + (hi - lo) // 2  # 向下取整
    if some_condition:
        lo = mid  # BUG! 可能导致死循环
    else:
        hi = mid - 1

为什么这么容易错？ 因为二分查找涉及三个互相耦合的决策：

1. 搜索区间的定义（开/闭）
2. 循环继续的条件
3. 中点归属哪一侧

这三个决策必须严格一致。任何一个不匹配，就会出 bug。而且这些 bug 往往只在极端情况下触发（数组长度为 1、target 不存在、target 在首尾），正常测试根本发现不了。

防错心法：选定一种写法（推荐左闭右开），记住它的所有细节，永远不要混搭。

2.2 bisect 模块源码分析

Python 的 bisect 模块是用纯 Python 写的（CPython 还有一个 C 加速版本）。让我们看看 bisect_left 的源码：

def bisect_left(a, x, lo=0, hi=None, *, key=None):
    """Return the index where to insert item x in list a, assuming a is sorted.

    The return value is such that all e in a[:i] have e < x, and all e in
    a[i:] have e >= x.  So if x already appears in the list, a.insert(i, x)
    will insert just before the leftmost x already there.
    """
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    if key is None:
        while lo < hi:
            mid = (lo + hi) // 2
            if a[mid] < x:
                lo = mid + 1
            else:
                hi = mid
    else:
        while lo < hi:
            mid = (lo + hi) // 2
            if key(a[mid]) < x:
                lo = mid + 1
            else:
                hi = mid
    return lo

几个关键点：

1. 使用左闭右开 [lo, hi)：hi 初始为 len(a)，循环条件是 lo < hi。
2. 中点计算用 (lo + hi) // 2：在 Python 中不用担心整数溢出（Python 的 int 是任意精度的），但在 C/Java 中需要用 lo + (hi - lo) // 2。
3. 只有两个分支：a[mid] < x 时 lo = mid + 1，否则 hi = mid。没有 == x 的特殊处理！这是 bisect_left 的精髓——即使找到了等于 x 的元素，也继续往左找。
4. Python 3.10+ 支持 key 参数：可以对元素做变换后再比较，类似 sorted(key=...)。

bisect_right 的唯一区别：

# bisect_left:
if a[mid] < x:   # 严格小于
    lo = mid + 1
else:
    hi = mid

# bisect_right:
if a[mid] <= x:  # 小于等于（多了等号）
    lo = mid + 1
else:
    hi = mid

就这一个 = 号的差别，决定了找的是"最左插入点"还是"最右插入点"。

2.3 二分查找在 sorted containers 中的应用

Python 标准库没有平衡二叉搜索树（如 C++ 的 std::set），但有一个非常流行的第三方库 sortedcontainers，它用"分段列表 + 二分查找"实现了 O(log n) 的插入和查找：

from sortedcontainers import SortedList

sl = SortedList([5, 1, 3, 7, 9])
# 自动排序：[1, 3, 5, 7, 9]

sl.add(4)        # O(log n) 插入
sl.remove(3)     # O(log n) 删除
sl.bisect_left(5)   # 二分查找
sl.irange(3, 7)     # 范围查询 [3, 7]

SortedList 的内部结构：

• 将数据分成多个"段"（每段大约 1000 个元素）
• 维护一个索引列表记录每段的最大值
• 查找时先对索引列表做二分找到目标段，再在段内做二分
• 插入/删除时可能需要拆分或合并段

这种设计在实际工程中比红黑树快得多，因为它对 CPU 缓存友好——连续内存的顺序访问远快于树节点的随机访问。

2.4 浮点数二分

二分查找不仅能用在离散数组上，还能用在连续区间上。此时我们不再担心 off-by-one 错误，而是关心精度。

例 1：求平方根

def sqrt_binary_search(x: float, eps: float = 1e-10) -> float:
    """用二分法求 x 的平方根"""
    if x < 0:
        raise ValueError("Cannot compute sqrt of negative number")
    if x == 0:
        return 0.0
    
    lo, hi = 0.0, max(1.0, x)  # 当 x < 1 时，sqrt(x) > x
    while hi - lo > eps:
        mid = (lo + hi) / 2
        if mid * mid < x:
            lo = mid
        else:
            hi = mid
    return (lo + hi) / 2

例 2：求方程零点

对于单调函数 f(x)，如果 f(a) 和 f(b) 异号，那么 [a, b] 之间必有零点：

def find_zero(f, a: float, b: float, eps: float = 1e-10) -> float:
    """在 [a, b] 上找 f 的零点，前提：f(a) 和 f(b) 异号"""
    assert f(a) * f(b) <= 0, "f(a) and f(b) must have different signs"
    
    for _ in range(100):  # 100 次迭代足够达到 10^-30 精度
        mid = (a + b) / 2
        if f(mid) * f(a) <= 0:
            b = mid
        else:
            a = mid
    return (a + b) / 2

# 用法：求 x³ - 2x - 5 = 0 在 [2, 3] 的根
root = find_zero(lambda x: x**3 - 2*x - 5, 2, 3)
# root ≈ 2.0945514815

浮点数二分的注意事项：

1. 不要用 while lo < hi（浮点数可能永远不相等），用 while hi - lo > eps 或固定迭代次数。
2. 固定迭代次数更稳健：64 次迭代可以在 double 精度范围内达到极限精度。
3. eps 的选择取决于问题精度要求。竞赛中通常要求 10⁻⁶ 或 10⁻⁹。

2.5 二分答案

二分查找最强大的应用不是在数组中找元素，而是"二分答案"——当答案具有单调性时，用二分法猜答案。

模式：如果答案为 x 可行，且 x+1 也可行，那就存在单调性，可以二分。

典型问题：最小化最大值

问题：将数组分成 k 个连续子数组，使得子数组的最大和最小。

def split_array(nums: list[int], k: int) -> int:
    """LeetCode 410: 分割数组的最大值"""
    
    def can_split(max_sum: int) -> bool:
        """如果每个子数组的和不超过 max_sum，能否分成 <= k 个？"""
        count = 1
        current = 0
        for num in nums:
            if current + num > max_sum:
                count += 1
                current = num
            else:
                current += num
        return count <= k
    
    # 答案的范围：[max(nums), sum(nums)]
    lo, hi = max(nums), sum(nums)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if can_split(mid):
            hi = mid       # mid 可行，尝试更小的
        else:
            lo = mid + 1   # mid 不可行，答案更大
    return lo

思路：

• 答案（最大子数组和）的范围是 [max(nums), sum(nums)]
• 对于某个候选答案 mid，贪心地检查能否将数组分成不超过 k 个子数组
• 如果可以，说明 mid 可能太大，尝试更小的值
• 如果不可以，说明 mid 太小，答案在右边

典型问题：最大化最小值

问题：在长度为 L 的路上放 n 头牛，使得相邻两头牛之间的最小距离最大。

def aggressive_cows(positions: list[int], n: int) -> int:
    """最大化最小距离"""
    positions.sort()
    
    def can_place(min_dist: int) -> bool:
        """如果相邻牛的最小距离 >= min_dist，能否放下 n 头牛？"""
        count = 1
        last = positions[0]
        for pos in positions[1:]:
            if pos - last >= min_dist:
                count += 1
                last = pos
        return count >= n
    
    lo, hi = 1, positions[-1] - positions[0]
    while lo < hi:
        mid = lo + (hi - lo + 1) // 2  # 向上取整！
        if can_place(mid):
            lo = mid       # mid 可行，尝试更大的
        else:
            hi = mid - 1   # mid 不可行，答案更小
    return lo

注意向上取整：当我们要找"最大的满足条件的值"时，如果用 lo = mid，必须向上取整 mid = lo + (hi - lo + 1) // 2，否则当 hi = lo + 1 时 mid = lo 导致死循环。

Level 3 · 深入理解

3.1 二分查找的历史

二分查找的历史比你想象的更曲折：

从"想法提出"到"正确实现"花了 16 年。从"被广泛使用"到"发现还有 bug"又花了 20 年。这告诉我们一个深刻的道理：简单的想法不等于简单的实现。

3.2 整数溢出 bug

这是计算机科学史上最著名的 bug 之一。

// Java 中经典的二分查找（JDK 1.2 ~ JDK 5）
int mid = (low + high) / 2;  // BUG!

当 low + high 超过 Integer.MAX_VALUE（2³¹ - 1 ≈ 21 亿）时，会发生整数溢出，得到负数，然后数组越界。

修复方法：

int mid = low + (high - low) / 2;  // 正确
// 或者
int mid = (low + high) >>> 1;      // 无符号右移，也正确

Python 程序员不用担心这个问题吗？ 在纯 Python 中确实不用，因为 Python 的 int 是任意精度的。但如果你：

• 用 numpy（固定精度整数）
• 用 ctypes 调用 C 库
• 在面试中用 C++/Java 实现

就必须记住这个 bug。

有趣的事实：这个 bug 在 Java 的 Arrays.binarySearch 中潜伏了 9 年才被发现（1997-2006）。原因是只有当数组超过 10 亿个元素时才会触发，而在 2006 年之前，很少有程序处理这么大的数组。

3.3 二分查找 vs 插值查找 vs 指数查找

二分查找（Binary Search）：

• 每次取中点
• 时间 O(log n)，最坏情况也是 O(log n)
• 对数据分布没有任何假设

插值查找（Interpolation Search）：

• 根据 target 的值估计位置：mid = lo + (target - arr[lo]) * (hi - lo) // (arr[hi] - arr[lo])
• 如果数据均匀分布，平均 O(log log n)
• 但如果数据分布极不均匀，最坏 O(n)

def interpolation_search(nums: list[int], target: int) -> int:
    lo, hi = 0, len(nums) - 1
    while lo <= hi and nums[lo] <= target <= nums[hi]:
        if nums[lo] == nums[hi]:
            if nums[lo] == target:
                return lo
            break
        
        # 估计 target 在区间中的位置
        mid = lo + (target - nums[lo]) * (hi - lo) // (nums[hi] - nums[lo])
        
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

指数查找（Exponential Search）：

• 先指数扩张找到一个包含 target 的范围，再在该范围内二分
• 适合无界或极大数组，以及 target 靠近开头的情况
• 时间 O(log k)，k 是 target 的实际位置

def exponential_search(nums: list[int], target: int) -> int:
    n = len(nums)
    if n == 0:
        return -1
    if nums[0] == target:
        return 0
    
    # 找到包含 target 的范围
    bound = 1
    while bound < n and nums[bound] <= target:
        bound *= 2
    
    # 在 [bound//2, min(bound, n-1)] 内二分
    lo, hi = bound // 2, min(bound, n - 1)
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

对比总结：

3.4 下界二分 vs 上界二分的统一框架

所有的二分查找问题都可以归结为一个统一的框架：找分界点。

想象一个布尔数组 [F, F, F, ..., F, T, T, T, ..., T]——左边全是 False，右边全是 True。我们要找的是第一个 True 的位置。

def first_true(lo: int, hi: int, predicate) -> int:
    """在 [lo, hi) 中找第一个使 predicate 返回 True 的位置。
    前提：存在分界点 k，使得 predicate(i) 对 i < k 为 False，对 i >= k 为 True。
    如果所有都是 False，返回 hi。"""
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if predicate(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

所有变体都是这个框架的特例：

# bisect_left: 第一个 >= target 的位置
bisect_left = first_true(0, len(nums), lambda i: nums[i] >= target)

# bisect_right: 第一个 > target 的位置
bisect_right = first_true(0, len(nums), lambda i: nums[i] > target)

# 找最后一个 <= target: first_true 的前一个位置
last_le = first_true(0, len(nums), lambda i: nums[i] > target) - 1

# 旋转数组找最小值
min_idx = first_true(0, len(nums), lambda i: nums[i] <= nums[-1])

统一框架的意义：你不需要记住 6 种不同的二分模板。只需要记住一个 first_true，然后根据问题构造合适的 predicate。

对于"找最后一个 True"：

def last_true(lo: int, hi: int, predicate) -> int:
    """在 [lo, hi] 中找最后一个使 predicate 返回 True 的位置。
    如果所有都是 False，返回 lo - 1。"""
    while lo < hi:
        mid = lo + (hi - lo + 1) // 2  # 向上取整！
        if predicate(mid):
            lo = mid
        else:
            hi = mid - 1
    return lo if predicate(lo) else lo - 1

为什么 last_true 要向上取整？ 因为当 lo + 1 == hi 时，如果向下取整 mid = lo，且 predicate(lo) 为 True，则 lo = mid = lo 不变——死循环。向上取整保证 mid = hi，避免了这个问题。

这是二分查找中最微妙的地方之一。记住规则：

• 找第一个 True → 向下取整 + hi = mid
• 找最后一个 True → 向上取整 + lo = mid

Level 4 · 专家视角

4.1 经典 off-by-one 错误和死循环

让我们系统地分析二分查找中所有可能出错的地方。

Case Study 1：死循环

# 意图：在 [lo, hi] 中找最后一个满足条件的值
lo, hi = 0, n - 1
while lo < hi:
    mid = (lo + hi) // 2      # 向下取整
    if condition(mid):
        lo = mid              # BUG: 可能死循环
    else:
        hi = mid - 1

# 当 lo = 3, hi = 4 时：
# mid = (3+4)//2 = 3
# 如果 condition(3) 为 True，lo = 3，区间不变 → 死循环！

修复：mid = (lo + hi + 1) // 2（向上取整）。

Case Study 2：漏查元素

# 意图：在 [lo, hi] 中找 target
lo, hi = 0, len(nums) - 1
while lo < hi:         # BUG: 当 lo == hi 时没有检查！
    mid = (lo + hi) // 2
    if nums[mid] == target:
        return mid
    elif nums[mid] < target:
        lo = mid + 1
    else:
        hi = mid - 1
# 如果 target 恰好在 lo == hi 的位置，就漏掉了

修复：while lo <= hi（但要注意跟其他部分匹配）。

Case Study 3：数组越界

# 意图：用 [lo, hi) 找目标
lo, hi = 0, len(nums)
while lo < hi:
    mid = (lo + hi) // 2
    if nums[mid] < target:
        lo = mid + 1
    elif nums[mid] > target:
        hi = mid
    else:
        return mid
return lo  # lo 可能等于 len(nums)！

# 调用者如果不检查 lo < len(nums) 就直接访问 nums[lo]，会越界

防错清单：

4.2 面试高频题详解

4.2.1 搜索旋转排序数组（LeetCode #33）

def search(nums: list[int], target: int) -> int:
    """
    旋转排序数组中搜索 target。
    关键：每次至少有一半是有序的。
    """
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] == target:
            return mid
        
        if nums[lo] <= nums[mid]:
            # [lo, mid] 有序
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:
            # [mid, hi] 有序
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

易错点：nums[lo] <= nums[mid] 中的等号。当 lo == mid（只剩两个元素）时，左半段只有一个元素，它是有序的。如果去掉等号，会把这种情况归入"右半段有序"，导致错误。

时间复杂度：O(log n)。

4.2.2 寻找峰值（LeetCode #162）

def find_peak_element(nums: list[int]) -> int:
    """
    峰值：比两边邻居都大的元素。
    nums[-1] = nums[n] = -∞。
    
    关键洞察：如果 nums[mid] < nums[mid+1]，
    那么 [mid+1, hi] 必有峰值（因为要么一直上升到末尾，
    末尾是边界=−∞，所以最后一个上升点就是峰值）。
    """
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] < nums[mid + 1]:
            lo = mid + 1   # 峰值在右边
        else:
            hi = mid       # 峰值在左边（含 mid）
    return lo

为什么这里用 lo < hi 而不是 lo <= hi？ 因为这里不是在找某个特定的值，而是在缩小范围，最终 lo == hi 时就是答案。

为什么不会死循环？ 因为 lo = mid + 1（永远前进）和 hi = mid（也可能不动，但 mid < hi 因为向下取整）。当 lo + 1 == hi 时，mid = lo，如果走 lo = mid + 1 = hi，循环结束；如果走 hi = mid = lo，也结束。

时间复杂度：O(log n)。

4.2.3 在排序数组中查找元素的第一个和最后一个位置（LeetCode #34）

def search_range(nums: list[int], target: int) -> list[int]:
    """找 target 的第一个和最后一个位置。"""
    
    def bisect_left_custom(nums, target):
        lo, hi = 0, len(nums)
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if nums[mid] < target:
                lo = mid + 1
            else:
                hi = mid
        return lo
    
    def bisect_right_custom(nums, target):
        lo, hi = 0, len(nums)
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if nums[mid] <= target:
                lo = mid + 1
            else:
                hi = mid
        return lo
    
    left = bisect_left_custom(nums, target)
    right = bisect_right_custom(nums, target) - 1
    
    if left <= right and left < len(nums) and nums[left] == target:
        return [left, right]
    return [-1, -1]

本质：就是 bisect_left 和 bisect_right - 1。这道题是考你对二分查找变体的理解。

时间复杂度：O(log n)，两次二分。

4.2.4 有效的完全平方数（LeetCode #367）

def is_perfect_square(num: int) -> bool:
    """判断 num 是否是完全平方数。"""
    lo, hi = 1, num
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        square = mid * mid
        if square == num:
            return True
        elif square < num:
            lo = mid + 1
        else:
            hi = mid - 1
    return False

优化：可以把上界设为 min(num, 46341)（因为 46341² > 2³¹ - 1）。或者对于大数，hi = num // 2 + 1（因为当 num >= 4 时，√num < num/2）。

注意：Python 中不用担心 mid * mid 溢出，但在 C++/Java 中需要用 long long 或者改成 mid == num / mid && num % mid == 0。

4.3 什么时候不该用二分

二分查找有明确的前提条件。违反这些条件时，它就不适用：

1. 数据未排序

二分查找的核心假设是"排除一半"。如果数据不是有序的（或没有某种单调性），你无法安全地排除任何一半。

例外：寻找峰值（#162）不需要全局有序，但利用了局部单调性。

2. 链表

链表无法 O(1) 访问中间元素。对链表做二分查找的时间复杂度是 O(n log n)（每次找中点要 O(n)），比顺序查找的 O(n) 还慢。

3. 频繁插入/删除的场景

如果需要频繁修改数据，维护排序的成本（每次 O(n) 的插入）可能超过二分查找节省的时间。此时应该用平衡二叉搜索树（如 SortedList）或跳表。

4. 数据量极小

当 n < 32 时，顺序查找可能比二分查找更快，因为：

• 没有分支预测失败的代价
• 缓存友好的顺序访问
• 代码更简单，CPU 流水线效率更高

实际工程中，很多排序算法对小数组会退化为插入排序而不是继续递归，同理，小数据量的查找直接遍历即可。

5. 需要找所有满足条件的元素

如果需要找到所有等于 target 的元素，二分找到一个后还是需要向两边扩展，最坏 O(n)。不如直接用 bisect_left + bisect_right 一次性确定范围。

4.4 二分答案的面试应用

4.4.1 分割数组的最大值（LeetCode #410）

这道题在 Level 2 已经给出了完整解法。让我们深入分析为什么它是正确的。

单调性证明：设 f(x) = "能否将数组分成 ≤ k 个子数组，每个子数组的和 ≤ x"。

• 如果 f(x) 为 True，那么对所有 y > x，f(y) 也为 True。（限制放宽了，当然更容易满足。）
• 因此 f 从某个点开始变为 True，之后一直为 True。
• 我们要找的是第一个使 f(x) 为 True 的 x。

这正是 first_true 框架！

def split_array(nums: list[int], k: int) -> int:
    def feasible(max_sum: int) -> bool:
        count = 1
        current = 0
        for num in nums:
            if current + num > max_sum:
                count += 1
                current = num
                if count > k:
                    return False
            else:
                current += num
        return True
    
    lo, hi = max(nums), sum(nums)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if feasible(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

时间复杂度：O(n log S)，其中 S = sum(nums) - max(nums)。

4.4.2 爱吃香蕉的珂珂（LeetCode #875）

问题：有 n 堆香蕉，第 i 堆有 piles[i] 个。警卫走了 h 小时后回来。珂珂每小时吃 k 个（一堆没吃完就不吃下一堆）。求最小的 k。

import math

def min_eating_speed(piles: list[int], h: int) -> int:
    """
    二分答案：猜每小时吃 k 个，验证能否在 h 小时内吃完。
    """
    
    def can_finish(k: int) -> bool:
        """以速度 k 能否在 h 小时内吃完所有香蕉？"""
        hours = sum(math.ceil(pile / k) for pile in piles)
        return hours <= h
    
    lo, hi = 1, max(piles)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if can_finish(mid):
            hi = mid       # 可以更慢
        else:
            lo = mid + 1   # 太慢了，需要更快
    return lo

分析：

• 答案范围：[1, max(piles)]。最慢每小时吃 1 个，最快每小时吃 max(piles) 个（一小时吃完最大堆）。
• 单调性：k 越大，需要的总时间越少。
• can_finish(k) 的时间 O(n)，二分的范围 O(log(max(piles)))。
• 总时间：O(n log M)，M = max(piles)。

易错点：math.ceil(pile / k) 要注意整数除法。在 Python 中可以用 (pile + k - 1) // k 或 math.ceil(pile / k)。前者避免浮点数问题。

4.4.3 识别"二分答案"的套路

当你在面试中遇到一道看起来很复杂的优化问题，检查以下条件：

1. 问题问的是"最小的最大值"或"最大的最小值" → 几乎一定是二分答案。
2. 答案有明确的范围 → 可以确定 lo 和 hi。
3. "给定答案 x，能否判断可行性"这个子问题比原问题简单得多 → 验证函数通常是贪心的。
4. 可行性具有单调性 → x 增大时可行性不会从 True 变 False（或反过来）。

更多二分答案经典题：

面试建议：

1. 先确认单调性，跟面试官沟通你的思路。
2. 写清楚 lo, hi 的含义和初始值。
3. 验证函数单独写成一个函数，保持主逻辑清晰。
4. 注意向上取整 vs 向下取整（取决于你是找第一个 True 还是最后一个 True）。

总结

二分查找是算法世界中"简单到出错"的典范。它的思想只有一句话：每次排除一半。但把它写对，需要对边界条件有极其精确的理解。

核心要点：

1. 选定一种模板，坚持使用。推荐左闭右开 + first_true 框架。
2. 区间定义决定一切。初始化、循环条件、边界更新必须匹配。
3. bisect_left 和 bisect_right 可以解决 95% 的问题。掌握它们的含义：第一个 >= target 的位置 vs 第一个 > target 的位置。
4. 二分答案是最强大的应用。当答案具有单调性时，猜答案 + 验证 = O(验证时间 × log 范围)。
5. 向上取整防死循环。当 lo = mid 时，必须 mid = lo + (hi - lo + 1) // 2。

最后记住 Jon Bentley 的教训：写完二分查找后，至少用这些 case 测试：

• 空数组
• 只有一个元素（等于/不等于 target）
• target 在第一个位置
• target 在最后一个位置
• target 不存在（比所有元素小 / 比所有元素大 / 在中间某两个元素之间）
• 所有元素相同