第4章：二分查找的变体

二分查找是算法中最优雅的技巧之一，它将线性搜索的 $O(n)$ 复杂度降低到 $O(\log n)$。但真正的威力不仅仅在于查找有序数组中的元素，而在于它可以应用于任何具有单调性质的问题。本章将深入探讨二分查找的各种变体，帮助你建立"二分思维"——识别隐藏的单调性，并将复杂问题转化为二分决策。

对于有函数式编程背景的工程师来说，二分查找本质上是一个高阶函数，它接受一个决策函数（predicate）并在定义域上找到满足条件的边界点。这种抽象视角将帮助我们更好地理解和应用二分查找。

1. 标准二分与边界处理

1.1 二分查找的本质

二分查找的核心思想是通过每次排除一半的搜索空间来快速定位目标。但在实际应用中，边界处理往往是最容易出错的地方。让我们从最基础的二分查找开始，建立正确的思维模型。

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  # 未找到

这个基础版本有几个关键点：

使用 left <= right 作为循环条件，确保搜索区间为闭区间 [left, right]
计算 mid 时使用 left + (right - left) // 2 避免溢出
更新边界时使用 mid + 1 和 mid - 1，因为 mid 已经检查过

1.2 查找边界的统一模板

在 LeetCode #34（在排序数组中查找元素的第一个和最后一个位置）中，我们需要找到目标值的左右边界。这里介绍一个统一的模板，可以处理各种边界查找问题：

def find_left_boundary(nums, target):
    """查找第一个大于等于target的位置"""
    left, right = 0, len(nums)  # 注意：right = len(nums)

    while left < right:  # 注意：不是 left <= right
        mid = left + (right - left) // 2
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid  # 注意：不是 mid - 1

    return left  # left == right，即第一个 >= target 的位置

def find_right_boundary(nums, target):
    """查找最后一个小于等于target的位置"""
    left, right = 0, len(nums)

    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] <= target:
            left = mid + 1
        else:
            right = mid

    return left - 1  # 最后一个 <= target 的位置

这个模板的优势在于：

搜索区间是左闭右开 [left, right)，更符合数学直觉
循环条件是 left < right，终止时 left == right
通过调整判断条件（< vs <=），可以灵活处理各种边界情况

1.3 实战应用：LeetCode #34

def searchRange(nums, target):
    """在排序数组中查找元素的第一个和最后一个位置"""
    if not nums:
        return [-1, -1]

    # 找到第一个 >= target 的位置
    left_bound = bisect_left(nums, target)

    # 检查是否找到target
    if left_bound >= len(nums) or nums[left_bound] != target:
        return [-1, -1]

    # 找到第一个 > target 的位置，再减1
    right_bound = bisect_left(nums, target + 1) - 1

    return [left_bound, right_bound]

def bisect_left(nums, target):
    """Python内置bisect_left的实现"""
    left, right = 0, len(nums)
    while left < right:
        mid = (left + right) // 2
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid
    return left

2. 二分答案：最大化最小值问题

2.1 问题模式识别

"最大化最小值"或"最小化最大值"是二分答案的典型应用场景。这类问题的特征是：

要求在某种约束下，找到最优的分配方案
答案具有单调性：如果答案为 k 可行，那么答案为 k-1（或 k+1）也可行
可以快速验证某个答案是否可行

2.2 核心思路：答案空间上的二分

不在输入数组上二分，而是在可能的答案空间上二分。这种思维转换是解决这类问题的关键。

def binary_search_answer(check_func, low, high):
    """在答案空间[low, high]上二分查找"""
    while low < high:
        mid = (low + high) // 2
        if check_func(mid):
            high = mid  # 答案可能更小
        else:
            low = mid + 1  # 答案需要更大
    return low

2.3 实战应用：LeetCode #875 爱吃香蕉的珂珂

def minEatingSpeed(piles, h):
    """
    珂珂吃香蕉问题：最小化吃香蕉的速度
    关键洞察：速度越快，时间越少（单调性）
    """
    def can_finish(speed):
        """判断以speed速度能否在h小时内吃完"""
        hours = 0
        for pile in piles:
            hours += (pile + speed - 1) // speed  # 向上取整
        return hours <= h

    # 答案空间：[1, max(piles)]
    left, right = 1, max(piles)

    while left < right:
        mid = (left + right) // 2
        if can_finish(mid):
            right = mid  # 可以更慢
        else:
            left = mid + 1  # 必须更快

    return left

2.4 实战应用：LeetCode #1011 在D天内送达包裹的能力

def shipWithinDays(weights, days):
    """
    最小化船的载重能力，使得能在days天内送完
    单调性：载重越大，需要的天数越少
    """
    def can_ship(capacity):
        """判断以capacity载重能否在days天内送完"""
        needed_days = 1
        current_weight = 0

        for weight in weights:
            if current_weight + weight > capacity:
                needed_days += 1
                current_weight = weight
            else:
                current_weight += weight

        return needed_days <= days

    # 答案空间：[max(weights), sum(weights)]
    # 最小：能装下最重的包裹
    # 最大：一次装下所有包裹
    left, right = max(weights), sum(weights)

    while left < right:
        mid = (left + right) // 2
        if can_ship(mid):
            right = mid
        else:
            left = mid + 1

    return left

3. 旋转数组与山峰数组

3.1 旋转数组的特性

旋转数组是将有序数组的前k个元素移到末尾得到的。关键特性：

数组被分成两个有序部分
至少有一半是有序的
可以通过比较中点与端点判断哪一半有序

3.2 LeetCode #33 搜索旋转排序数组

def search(nums, target):
    """
    在旋转数组中查找目标值
    核心：判断哪一半是有序的，然后决定搜索方向
    """
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = (left + right) // 2

        if nums[mid] == target:
            return mid

        # 判断哪一半是有序的
        if nums[left] <= nums[mid]:  # 左半部分有序
            # 判断target是否在左半部分
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:  # 右半部分有序
            # 判断target是否在右半部分
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1

    return -1

3.3 山峰数组：LeetCode #162 寻找峰值

山峰数组的特点是先递增后递减。寻找峰值的关键洞察：

如果 nums[mid] < nums[mid + 1]，右侧必有峰值
如果 nums[mid] > nums[mid + 1]，左侧（包括mid）必有峰值

def findPeakElement(nums):
    """
    寻找峰值元素
    关键：向"更高"的方向移动必定能找到峰值
    """
    left, right = 0, len(nums) - 1

    while left < right:
        mid = (left + right) // 2

        if nums[mid] < nums[mid + 1]:
            # 右侧更高，峰值在右侧
            left = mid + 1
        else:
            # 左侧更高或mid就是峰值
            right = mid

    return left

4. 二分查找的抽象：单调性与决策函数

4.1 抽象思维：从具体到一般

二分查找的本质不是"在有序数组中查找"，而是"在单调函数上找边界"。这个函数可以是：

数组索引到值的映射（标准二分）
答案到可行性的映射（二分答案）
任何具有单调性的决策函数

4.2 决策函数的设计

关键是设计一个函数 f(x)，使得：

对于 x < boundary，f(x) = False
对于 x >= boundary，f(x) = True
我们要找的就是这个 boundary

def abstract_binary_search(predicate, low, high):
    """
    抽象的二分查找
    predicate: 决策函数，返回 True/False
    返回：第一个使 predicate 为 True 的位置
    """
    while low < high:
        mid = (low + high) // 2
        if predicate(mid):
            high = mid
        else:
            low = mid + 1
    return low

4.3 实战应用：LeetCode #287 寻找重复数

这道题展示了二分查找的创造性应用：

def findDuplicate(nums):
    """
    寻找重复数（数组包含n+1个数，范围是[1,n]）
    关键洞察：如果没有重复，<=k的数最多有k个
    如果有重复且重复数<=k，则<=k的数会超过k个
    """
    n = len(nums) - 1
    left, right = 1, n

    while left < right:
        mid = (left + right) // 2

        # 统计 <= mid 的数的个数
        count = sum(1 for num in nums if num <= mid)

        if count > mid:
            # 重复数在 [left, mid]
            right = mid
        else:
            # 重复数在 [mid+1, right]
            left = mid + 1

    return left

4.4 实战应用：LeetCode #378 有序矩阵中第K小的元素

def kthSmallest(matrix, k):
    """
    有序矩阵中第K小的元素
    关键：二分答案值，统计<=mid的元素个数
    """
    n = len(matrix)

    def count_less_equal(target):
        """统计矩阵中<=target的元素个数"""
        count = 0
        row = n - 1  # 从左下角开始
        col = 0

        while row >= 0 and col < n:
            if matrix[row][col] <= target:
                count += row + 1  # 整列都<=target
                col += 1
            else:
                row -= 1

        return count

    # 在值域上二分
    left, right = matrix[0][0], matrix[-1][-1]

    while left < right:
        mid = (left + right) // 2

        if count_less_equal(mid) < k:
            left = mid + 1
        else:
            right = mid

    return left

本章小结

二分查找的威力远超在有序数组中查找元素。掌握二分思维的关键在于：

识别单调性：不仅是数组的有序性，更是问题的单调性质
设计决策函数：将问题转化为"是否满足条件"的判断
选择搜索空间：可以是索引空间、答案空间或值域空间
处理边界条件：理解开闭区间的差异，选择合适的模板

核心公式和复杂度：

时间复杂度：$O(\log n)$ 其中 n 是搜索空间大小
空间复杂度：$O(1)$
迭代次数：$\lceil \log_2 n \rceil$

记住：二分查找是一种思维方式，而不仅仅是一个算法。当你发现问题具有单调性质时，就应该考虑能否应用二分查找。

常见陷阱与错误 (Gotchas)

1. 边界处理错误

最常见的错误是混淆开闭区间：

# 错误示例
while left <= right:  # 闭区间
    mid = (left + right) // 2
    if check(mid):
        right = mid  # 错误！应该是 mid - 1

解决方案：选择一个模板并坚持使用

闭区间 [left, right]：使用 left <= right，更新为 mid ± 1
半开区间 [left, right)：使用 left < right，更新为 mid 或 mid + 1

2. 整数溢出

# 潜在溢出
mid = (left + right) // 2

# 安全写法
mid = left + (right - left) // 2

3. 死循环

当 left = right - 1 时，如果不正确更新边界，可能陷入死循环：

# 可能死循环
while left < right:
    mid = (left + right) // 2
    if check(mid):
        left = mid  # 当 left = right - 1 时，mid = left，无限循环

解决方案：

使用 mid = (left + right + 1) // 2 向上取整
或确保每次迭代都能缩小区间

4. 答案不存在的处理

# 忘记检查答案是否存在
result = binary_search(nums, target)
# 应该检查 result 是否有效
if result < len(nums) and nums[result] == target:
    # 找到了

5. 二分答案的精度问题

对于浮点数二分，需要考虑精度：

# 浮点数二分
while right - left > 1e-6:  # 不是 left < right
    mid = (left + right) / 2.0
    if check(mid):
        right = mid
    else:
        left = mid

调试技巧

打印搜索区间：在循环中打印 [left, right] 观察区间收敛
检查单调性：确认你的判断函数确实具有单调性
边界测试：测试空数组、单元素、两元素的情况
手动模拟：对小数据手动执行算法，检查逻辑

记住：二分查找看似简单，但细节决定成败。选择一个你理解的模板，并在实践中不断熟练。