第 22 课 - 二分查找

所属模块： 搜索算法 难度： Beginner 标签： binary-search, sorted, mid

1. 学习目标

学完本节课，你将能够：

理解二分查找算法的核心思想及其与线性搜索的本质区别。
掌握在有序数组中实现二分查找的基本步骤。
编写正确的、可处理常见边界情况的二分查找代码。
分析二分查找的时间复杂度，并了解其应用场景与限制。

2. 核心概念

想象你在一本厚厚的、按页码顺序排列的字典里查找一个单词“apple”。

线性搜索就像从第一页开始，一个词一个词地向后翻，直到找到“apple”。如果它不在字典里，你需要翻完所有页。
二分查找则聪明得多：你首先翻开字典的正中间。如果“apple”在你看到的页面的某个单词之前，你就知道只需要在前半部分寻找；如果“apple”在后面，你就只关注后半部分。接着，你重复这个过程，每次都将搜索范围缩小一半，直到找到目标或者确认它不存在。

核心前提： 二分查找仅适用于有序的数组（例如，数字从小到大排列）。如果数组无序，二分查找将无法正确工作。

算法步骤：

初始化： 设置两个指针，left 指向数组起始索引（0），right 指向数组最后一个元素的索引（len(arr) - 1）。
循环： 当 left <= right 时，重复以下步骤：
- 计算中间位置：mid = (left + right) // 2。
- 比较：
  - 如果 arr[mid] 等于目标值，恭喜，直接返回 mid。
  - 如果目标值小于 arr[mid]，说明目标值在左半边，将 right 更新为 mid - 1。
  - 如果目标值大于 arr[mid]，说明目标值在右半边，将 left 更新为 mid + 1。
结束： 如果循环结束仍未找到，说明目标值不在数组中，返回一个特殊值（如 -1）。

时间复杂度： O(log n)。因为每次比较都将搜索范围减半，即使数据量翻倍，查找也只需要多进行一次比较。这比线性搜索的 O(n) 高效得多，尤其是在处理海量数据时。

3. 代码示例

下面是一个完整的Python实现，包含详细注释和测试用例。

def binary_search(arr, target):
    """
    在有序数组 arr 中查找目标值 target。
    如果找到，返回其索引；否则返回 -1。
    """
    left = 0
    right = len(arr) - 1

    while left <= right:
        # 计算中间索引。使用 (left + right) // 2 避免整数溢出
        mid = (left + right) // 2

        # 检查中间元素是否是目标值
        if arr[mid] == target:
            return mid
        # 如果目标值比中间元素小，搜索左半部分
        elif target < arr[mid]:
            right = mid - 1
        # 如果目标值比中间元素大，搜索右半部分
        else:
            left = mid + 1

    # 循环结束仍未找到
    return -1

# 测试代码
if __name__ == "__main__":
    # 一个有序数组
    sorted_list = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]

    # 测试用例1：查找存在的元素
    target1 = 23
    result1 = binary_search(sorted_list, target1)
    print(f"在数组 {sorted_list} 中查找 {target1}: 索引为 {result1}") # 预期输出：索引为 5

    # 测试用例2：查找不存在的元素
    target2 = 100
    result2 = binary_search(sorted_list, target2)
    print(f"在数组 {sorted_list} 中查找 {target2}: 索引为 {result2}") # 预期输出：索引为 -1

    # 测试用例3：查找第一个和最后一个元素
    target3 = 2
    result3 = binary_search(sorted_list, target3)
    print(f"查找第一个元素 {target3}: 索引为 {result3}") # 预期输出：索引为 0

    target4 = 91
    result4 = binary_search(sorted_list, target4)
    print(f"查找最后一个元素 {target4}: 索引为 {result4}") # 预期输出：索引为 9

4. 实践练习

练习 1：基础实现 修改上面的 binary_search 函数，使其返回一个布尔值 True 或 False，表示目标值是否存在于数组中。

要求： 函数名改为 binary_search_exists，只接受 arr 和 target 两个参数。

示例输出：

print(binary_search_exists([1, 3, 5, 7], 3)) # 输出: True
print(binary_search_exists([1, 3, 5, 7], 4)) # 输出: False

练习 2：查找所有匹配项（变体思考） 给定一个可能包含重复元素的有序数组，写一个函数 find_all_indices，返回目标值在数组中的所有索引的列表。如果不存在，返回空列表。

提示： 这是下一课“二分查找变体”的预热。一个思路是：找到一个匹配项后，以此为中心向左右两边线性扫描。

示例输出：

print(find_all_indices([1, 2, 2, 2, 3, 4], 2)) # 输出: [1, 2, 3]
print(find_all_indices([1, 2, 2, 2, 3, 4], 5)) # 输出: []

练习 3：递归实现 使用递归的方式实现二分查找函数 binary_search_recursive(arr, target, left=0, right=None)。

要求： 函数签名如上，right 的默认值应为 len(arr)-1。返回目标值的索引，或 -1。
提示： 递归的基准情况是 left > right（未找到）或 arr[mid] == target（找到）。

5. 常见错误

对无序数组使用二分查找： 这是最严重的错误。请永远记住，二分查找要求数组必须是有序的。在使用前，如果不能保证输入数组有序，应该先排序（但排序本身会消耗时间，需权衡）。
中间点计算溢出： 在某些语言中（如C++、Java），(left + right) / 2 当 left 和 right 都很大时可能产生整数溢出。更安全的写法是 left + (right - left) // 2。Python的整数可以无限大，所以通常没有这个问题，但养成好习惯很重要。
边界条件错误： 最常见的错误是循环条件和指针更新错误。
- 错误循环条件： while left < right。这会漏掉 left == right 的情况，而该位置正是我们需要检查的最后一个元素。
- 错误指针更新： 将 right = mid 或 left = mid 而不是 mid-1 或 mid+1。这会导致 mid 位置在下次循环中被重复检查，甚至造成死循环。
整数除法与索引： 计算 mid 时，使用整数除法（//）至关重要。如果使用 /，会得到浮点数，不能作为索引。

6. 小结

二分查找是一种在有序数组中高效查找目标值的算法，其核心思想是分治，每次将搜索范围缩小一半。
时间复杂度为 O(log n)，远优于线性搜索的 O(n)，特别适合处理大规模数据。
实现关键在于维护 left 和 right 两个指针，通过比较中间值 arr[mid] 与目标值，不断调整搜索范围。
适用条件严格：仅适用于有序数组。且查找的是值，不是索引本身（数组索引是连续的，但值是有序的即可）。
掌握二分查找是理解更高级变体（如查找第一个/最后一个等于目标值的位置、在旋转数组中查找等）的基础。

现在，你已经掌握了二分查找的精髓。在下一课，我们将探索它的一些有趣变体，以解决更复杂的问题！

练习编辑器

rust