查找算法：二分查找及其变体
查找算法：二分查找及其变体
查找算法是计算机科学中最基本、最常用的操作之一。它的目标是从一个数据集合中，找出满足特定条件的元素。面对不同特性的数据，我们需要选择不同的查找策略。本文将深入讲解最经典的二分查找算法，分析它的原理、实现和边界处理，并介绍几种在实际开发中非常实用的变体。
为什么需要二分查找
假设你有一本包含100万个单词的词典，要查找单词"Algorithm"。如果从第一页开始一页一页翻找（线性查找），最坏情况下你需要翻完一整本书。而二分查找将这本词典视为一个有序集合，每次都从中间翻开，判断目标单词在左边还是右边，瞬间就能砍掉一半的搜索范围。这就是二分查找的核心思想：在有序数据中，通过不断将搜索区间对半分，快速逼近目标值。
线性查找的时间复杂度是 O(n)，而二分查找仅为 O(log n)。当数据量从1万增长到100万，线性查找的耗时可能从1秒变为100秒，而二分查找只需要从约14次比较增加到约20次。对数级增长的威力，使它成为处理大规模有序数据的首选查找方式。
经典二分查找
基本思想与前置条件
二分查找的运作依赖于一个牢不可破的前提：数据必须有序（通常为升序）。算法维护一个搜索区间 [left, right]，每次取中间位置 mid，将目标值 target 与 arr[mid] 比较：
- 若相等，查找成功，返回
mid； - 若
target < arr[mid]，说明目标值在左半区间，将右边界收缩到mid - 1； - 若
target > arr[mid]，说明目标值在右半区间，将左边界收缩到mid + 1。
循环直到区间无效（left > right），表示目标不存在，返回 -1。
标准实现 (Python)
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) // 2 # 防止整数溢出
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
实现细节：
- 使用
left + (right - left) // 2而非(left + right) // 2，是为了避免在强类型语言中left + right溢出。 - 循环条件是
left <= right，保证区间内至少有一个元素时继续搜索。当left > right时，元素一定不在数组中。
时间复杂度与空间复杂度
- 时间复杂度：O(log n)，每次比较将搜索空间减半。
- 空间复杂度：迭代版本为 O(1)，仅需常数级额外空间。递归版本因调用栈深度为 O(log n)。
常见误区与边界陷阱
二分查找看似简单，实则容易出错。以下几个点需要特别警惕：
-
循环终止条件
while left <= right还是while left < right？标准查找要求区间内所有元素都被检查，若采用<，当left == right时循环会跳出，漏掉最后一个元素。 -
中间值的计算
务必使用left + (right - left) // 2防止溢出。在地板除和天花板除的选择上，标准版本使用向下取整即可。 -
边界更新
收缩边界必须是mid + 1或mid - 1。如果错误地写成left = mid或right = mid，可能造成死循环，特别是在left和right相邻时。
二分查找的常见变体
标准二分查找解决“是否存在某个值”的问题。但实际场景往往更复杂：我们需要找到第一个等于目标的位置、最后一个等于目标的位置、第一个大于目标的位置等。这些变体只需在标准版本上微调边界移动和返回值逻辑。
变体一：查找第一个等于目标值的元素
当数组中可能存在重复元素时，普通二分查找可能返回任意一个匹配位置。要找到第一个等于 target 的索引，核心思路是：即使 arr[mid] == target，也不要立即返回，而是继续向左搜索，直到锁定左边界。
def first_equal(arr, target):
left, right = 0, len(arr) - 1
result = -1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
result = mid # 记录当前找到的位置
right = mid - 1 # 继续向左找
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return result
变体二：查找最后一个等于目标值的元素
与变体一对称，当 arr[mid] == target 时，向右收缩左边界，记录当前位置。
def last_equal(arr, target):
left, right = 0, len(arr) - 1
result = -1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
result = mid
left = mid + 1 # 继续向右找
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return result
变体三：查找第一个大于等于目标值的元素 (下界)
这个变体常用于寻找插入位置或下界。即使数组中没有 target，我们也想知道它应该被放置在哪个索引，以保持有序。
def lower_bound(arr, target):
left, right = 0, len(arr) # 注意右边界初始化为 len(arr)
while left < right:
mid = left + (right - left) // 2
if arr[mid] < target:
left = mid + 1
else:
right = mid
return left # 循环结束时 left == right，即为下界
区别：这里右边界设为 len(arr)，因为目标值可能大于所有元素，此时插入位置在最末尾。循环条件变为 left < right，避免死循环。返回值是第一个不小于 target 的位置。
变体四：查找第一个大于目标值的元素 (上界)
与下界类似，但要求严格大于。只需将条件中的 < 改为 <=：
def upper_bound(arr, target):
left, right = 0, len(arr)
while left < right:
mid = left + (right - left) // 2
if arr[mid] <= target:
left = mid + 1
else:
right = mid
return left
变体五：旋转排序数组中的二分查找
一个原本升序的数组在某个未知点进行了旋转，比如 [4,5,6,7,0,1,2]。虽然整体不再有序，但局部有序仍然存在。我们可以在二分时判断哪一半是正常有序的，从而决定搜索方向。
def search_rotated(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
return mid
# 左半部分有序
if arr[left] <= arr[mid]:
if arr[left] <= target < arr[mid]:
right = mid - 1
else:
left = mid + 1
# 右半部分有序
else:
if arr[mid] < target <= arr[right]:
left = mid + 1
else:
right = mid - 1
return -1
核心在于通过比较 arr[left] 和 arr[mid] 来确定哪一段是单调递增的，然后判断目标是否落在该区间内。
实践建议与总结
- 优先使用标准库：Python的
bisect模块提供了bisect_left、bisect_right，成熟可靠。 - 手写时画图：用具体例子追踪
left、right、mid的变化，能有效避免死循环和越界。 - 理解变体的本质：所有变体都是对“相等时如何处理”以及“边界如何收缩”的调整。掌握了
lower_bound的写法，就能推导出大部分变体。
二分查找是算法设计的缩影：看似简单，却蕴含着边界处理、不变量维护和复杂问题分解的深刻智慧。熟练运用它，不仅能提高编码效率，更能锻炼严谨的逻辑思维能力。