二分查找及其变体

简介

二分查找（Binary Search）是一种在有序集合中高效查找目标元素的算法，其核心思想是通过不断将搜索区间对半分割来缩小范围，从而将时间复杂度从线性查找的 O(n) 降至 O(log n)。这种算法不仅是解决简单查找问题的利器，更是一种强大的算法范式，其应用场景远超在有序数组中寻找单一元素。

理解二分查找的关键在于掌握其循环不变量与边界条件，这是写出正确、无死循环代码的基础。更重要的是，二分查找的思想可以延伸至多种变体，例如寻找目标值的左边界或右边界，以及在部分有序（如旋转数组）或未明确排序但具有特定单调性的问题中应用。更进一步，二分查找可以作为一种搜索策略，应用于“答案空间”上，将复杂的最优化问题（如“最小化最大值”）转化为更简单的判定问题，极大地拓展了其解决问题的范围。本章将系统性地讲解标准二分查找及其四大变体，并通过实战例题深化理解。

核心概念

循环不变量与边界条件

循环不变量（Loop Invariant）是保证算法正确性的核心概念。在二分查找中，它通常被定义为：在每一次循环开始时，目标元素（如果存在）一定位于当前的搜索区间 [left, right] 内。维护这个不变量是设计边界更新逻辑的指导原则。

边界条件的处理是二分查找最容易出错的地方，主要体现在 while 循环的条件是 left <= right 还是 left < right，以及更新 left 和 right 时是 mid + 1、mid - 1 还是 mid。这通常由搜索区间的定义决定： - 闭区间 [left, right]：循环条件为 while left <= right，更新时 left = mid + 1，right = mid - 1。区间为空时终止。 - 左闭右开区间 [left, right)：循环条件为 while left < right，更新时 left = mid + 1，right = mid。当 left == right 时区间为空。

选择一种定义并始终坚持，是避免错误的关键。下图展示了标准二分查找在闭区间定义下的决策流程：

四大变体

1. 标准二分查找：在有序无重复数组中，查找目标值是否存在，返回任意一个匹配的索引。
2. 寻找左边界：在有序数组（可能包含重复值）中，查找目标值第一次出现的位置。若不存在，返回应插入的位置以保持有序（即 bisect_left）。
3. 寻找右边界：在有序数组（可能包含重复值）中，查找目标值最后一次出现的位置的后一个位置（即 bisect_right）。
4. 旋转数组搜索：数组在某个点旋转后（如 [4,5,6,7,0,1,2]），它不再是全局有序，但至少有一半总是有序的。利用这个性质，我们可以先判断哪一半有序，再检查目标是否位于该有序区间内。

在“答案空间”上二分

这是二分查找最精妙的应用之一。对于某些最优化问题（例如，“使得……最大的最小值”或“使得……最小的最大值”），我们可能无法直接计算答案，但可以很容易地判定一个给定的候选答案 x 是否可行。此时，我们可以： 1. 确定答案的可能范围 [min_val, max_val]。 2. 在这个范围上进行二分查找。 3. 对于每个 mid，将其作为候选答案，调用判定函数 check(mid)。 4. 根据 check(mid) 的结果（True 或 False）来收缩搜索区间，最终逼近最优解。 这种方法将求解问题转化为一系列判定问题，极大地简化了思维难度。

实战示例

示例1：标准二分查找与寻找左右边界

以下代码展示了标准二分查找及其寻找左右边界变体的实现，注意区间定义和边界更新的区别。

def binary_search_standard(nums, target):
"""
标准二分查找（闭区间写法）。
在有序数组 nums 中查找 target，找到则返回索引，否则返回 -1。
"""
left, right = 0, len(nums) - 1  # 定义闭区间 [left, right]
while left <= right:  # 区间为空时终止
mid = left + (right - left) // 2  # 防止溢出
if nums[mid] == target:
return mid  # 找到目标
elif nums[mid] < target:
left = mid + 1  # 目标在右半部分
else:  # nums[mid] > target
right = mid - 1  # 目标在左半部分
return -1  # 未找到
def binary_search_left_bound(nums, target):
"""
寻找左边界（左闭右开区间写法）。
返回 target 第一次出现的位置，若不存在则返回其应插入的位置。
"""
left, right = 0, len(nums)  # 定义左闭右开区间 [left, right)
while left < right:  # 当 left == right 时区间为空
mid = left + (right - left) // 2
if nums[mid] < target:
left = mid + 1  # 搜索区间变为 [mid+1, right)
else:  # nums[mid] >= target
right = mid  # 搜索区间变为 [left, mid)，注意包含等于时右边界左移
# 循环结束时，left 是第一个 >= target 的元素索引
return left  # 对于查找插入位置，直接返回 left 即可
def binary_search_right_bound(nums, target):
"""
寻找右边界（左闭右开区间写法）。
返回 target 最后一次出现位置的下一个索引。
"""
left, right = 0, len(nums)
while left < right:
mid = left + (right - left) // 2
if nums[mid] <= target:
left = mid + 1  # 搜索区间变为 [mid+1, right)，等于时左边界右移
else:  # nums[mid] > target
right = mid  # 搜索区间变为 [left, mid)
# 循环结束时，left 是第一个 > target 的元素索引
# 右边界即为 left - 1
return left - 1 if left > 0 and nums[left - 1] == target else -1
# 测试代码
if __name__ == "__main__":
sorted_nums = [1, 2, 3, 4, 4, 4, 5, 6, 7]
target = 4
print(f"有序数组: {sorted_nums}")
print(f"查找目标: {target}")
print(f"标准查找索引: {binary_search_standard(sorted_nums, target)}")
print(f"左边界索引: {binary_search_left_bound(sorted_nums, target)}")
print(f"右边界索引: {binary_search_right_bound(sorted_nums, target)}")
# 测试不存在的目标
print(f"\n查找目标: 8 (不存在)")
print(f"左边界/插入位置: {binary_search_left_bound(sorted_nums, 8)}")

示例2：在“答案空间”上二分 - “分割数组的最大值”（LeetCode 410）

问题：给定一个非负整数数组 nums 和一个整数 k，你需要将数组分成 k 个连续的非空子数组。设计算法使得这 k 个子数组各自和的最大值最小，并返回这个最小值。

思路：我们无法直接求出这个最小的最大值。但我们可以判定：给定一个候选的最大子数组和 max_sum，我们能否在满足“每个子数组和不超过 max_sum”的前提下，将数组分成 k 份（或更少）？如果可以，说明真正的答案可能小于等于 max_sum；如果不可以，说明真正的答案必须大于 max_sum。这就在答案空间（可能的 max_sum 范围）上建立了单调性，可以使用二分查找。

def split_array(nums, k):
"""
使用二分查找在答案空间上求解分割数组的最大值的最小值。
"""
def can_split(max_allowed_sum):
"""
判定函数：当子数组和限制为 max_allowed_sum 时，能否在 k 份内分割完数组。
"""
current_sum = 0
pieces = 1  # 至少需要 1 份
for num in nums:
if current_sum + num > max_allowed_sum:
# 当前子数组加入 num 会超限，必须从 num 开始新的子数组
pieces += 1
current_sum = num
if pieces > k:  # 如果需要的份数已经超过 k，则不可能
return False
else:
current_sum += num
return True  # 能在 k 份内完成分割
# 答案空间的下界：任何一份至少包含一个元素，所以下界是数组中的最大值。
# 答案空间的上界：最差情况是不分割，所以上界是整个数组的和。
left, right = max(nums), sum(nums)
# 二分查找最小的可行 max_allowed_sum
while left < right:  # 左闭右开区间 [left, right)
mid = left + (right - left) // 2
if can_split(mid):
# 如果 mid 可行，说明答案可能更小，搜索左半部分
right = mid
else:
# 如果 mid 不可行，答案必须更大，搜索右半部分
left = mid + 1
# 循环结束时 left == right，即为最小的可行值
return left
# 测试代码
if __name__ == "__main__":
nums = [7, 2, 5, 10, 8]
k = 2
result = split_array(nums, k)
print(f"数组: {nums}")
print(f"分割份数 k: {k}")
print(f"子数组和最大值的最小可能值: {result}")
# 解释：一种最优分割是 [7,2,5] 和 [10,8]，和分别为 14 和 18，最大值为 18。
# 另一种是 [7,2,5,10] 和 [8]，和分别为 24 和 8，最大值为 24。
# 目标是找到最小的最大值，即 18。

对比分析

下表总结了二分查找不同变体与应用场景的关键区别：

最佳实践

• 统一区间定义：在同一个问题或代码库中，尽量坚持使用一种区间定义（如左闭右开 [left, right)），以减少思维切换带来的错误。
• 防止整数溢出：计算中点时使用 mid = left + (right - left) // 2 而非 (left + right) // 2，避免 left + right 可能的大数溢出。
• 仔细设计判定函数：在“答案空间二分”中，判定函数 check(mid) 的设计是解题的核心。它必须具有单调性：通常，如果 mid 可行，那么所有大于（或小于）mid 的值也应可行（或不可行）。
• 理解终止状态：明确二分查找结束时 left 和 right 指针的状态。例如，在寻找左边界的左闭右开写法中，循环结束时 left 指向第一个不小于目标值的元素，这正好是插入位置。
• 善用库函数：在 Python 中，bisect 模块提供了高效的二分查找实现（bisect_left, bisect_right），在解决标准查找和插入问题时可以直接使用。

小结

二分查找远不止于在有序数组中寻找元素。通过深入理解其循环不变量与边界条件，我们可以掌握其四大经典变体：标准查找、寻找左右边界以及旋转数组搜索。更重要的是，掌握“在答案空间上二分”这一范式，能够将许多复杂的最优化问题转化为简单的判定问题，极大地提升了我们解决算法问题的能力。实践时，牢记一种区间定义，注意防止溢出，并仔细设计判定函数的单调性，是写出正确、高效二分查找代码的关键。

下一节：深度优先搜索与回溯算法