二分查找：在有序名单里“猜数字”快速定位

什么是二分查找？

假设你有一本按字母顺序排好的电话簿，想找“小明”的电话。你会从第一页开始一页一页翻吗？当然不会！你会直接翻到中间，看看这一页上的名字，如果比“小明”大，就往前半本找；如果比“小明”小，就往后半本找。每次都能扔掉一半，很快就能找到。

二分查找（Binary Search）就是这种思路的编程实现：在一个有序的列表中，每次取中间的元素和要找的目标比较，根据大小关系缩小一半范围，直到找到目标或确定不存在。它就像一个“猜数字”游戏——你心里想一个1~100之间的数，我猜50，你说“大了”或“小了”，我就把范围砍掉一半，继续猜中间的数。

二分查找的效率非常高，时间复杂度是 O(log n)。什么意思呢？如果一个列表有1000个元素，最坏情况下只需要比较10次（因为2^10=1024）；如果有100万个元素，也只需要比较20次左右。比从头到尾的“顺序查找”（O(n)）快得多。

但二分查找有一个非常重要的前提：列表必须是有序的（从小到大或从大到小）。如果列表乱糟糟的，这个方法就完全失灵了。

核心思想：每次砍掉一半

用数学语言说，二分查找的步骤如下：

1. 设定查找范围的左边界 left（起始下标）和右边界 right（结束下标）。
2. 计算中间位置 mid = (left + right) // 2（整数除法，向下取整）。
3. 检查 arr[mid] 是否等于目标：
   • 如果相等，返回 mid（找到了）。
   • 如果 arr[mid] 比目标小，说明目标在右边，于是把 left 移到 mid + 1。
   • 如果 arr[mid] 比目标大，说明目标在左边，于是把 right 移到 mid - 1。
4. 重复步骤2~3，直到 left > right（说明范围为空，没找到），返回 -1。

这个过程就像玩“猜数字”时不断缩小范围，每次都能排除一半的可能性。

生活中的例子：查字典找“apple”

假设字典里单词按字母顺序排列，你要找“apple”。你会：

• 翻到字典中间（比如“m”开头的单词），发现“m”比“a”大。
• 于是扔掉后半本，只用前半本（从“a”到“l”）。
• 再翻到前半本的中间，比如“f”开头，还是比“a”大，再扔掉一半……
• 直到找到“a”开头的区域，再继续定位具体单词。

二分查找就是这么工作的，只不过它针对的是数字或可以比较大小的任何数据。

具体实现步骤（伪代码）

我们用一个数字列表来模拟：arr = [2, 5, 8, 12, 16, 23, 38, 45, 56, 72]，要找 target = 23。

• 初始：left = 0，right = 9（数组长度10，下标0~9）。
• 第1轮：mid = (0+9)//2 = 4，arr[4] = 16。16 < 23，所以目标在右边，left = 5。
• 第2轮：left = 5，right = 9，mid = (5+9)//2 = 7，arr[7] = 45。45 > 23，所以目标在左边，right = 6。
• 第3轮：left = 5，right = 6，mid = (5+6)//2 = 5，arr[5] = 23。相等！返回下标5。

只用了3次比较就找到了，而顺序查找需要6次（从0开始数到5）。

Python代码实现（非递归版）

下面是最常用的非递归写法（也叫迭代版）。注意每一行变量定义都有中文注释，方便你理解。

def binary_search(arr, target):
    """
    在有序列表arr中查找target，返回下标，未找到返回-1
    """
    left = 0                  # 左边界初始为0
    right = len(arr) - 1      # 右边界初始为数组最后一个下标

    while left <= right:                       # 只要范围非空就继续
        mid = (left + right) // 2               # 取中间位置（向下取整）
        if arr[mid] == target:                 # 找到了！
            return mid
        elif arr[mid] < target:                # 目标在右边一半
            left = mid + 1
        else:                                  # 目标在左边一半
            right = mid - 1

    return -1                                  # 没找到，返回-1

# 示例
nums = [2, 5, 8, 12, 16, 23, 38, 45, 56, 72]
index = binary_search(nums, 23)
print(f"23在列表中的下标是{index}")  # 输出：5

# 再试一个不存在的数
index2 = binary_search(nums, 99)
print(f"99在列表中的下标是{index2}")  # 输出：-1

递归版（了解即可）

二分查找也可以用递归实现，逻辑是一样的，只是用函数调用代替循环：

def binary_search_recursive(arr, target, left, right):
    if left > right:                # 空区间，没找到
        return -1
    mid = (left + right) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        return binary_search_recursive(arr, target, left, mid - 1)

# 调用示例（注意传入left和right）
nums = [2, 5, 8, 12, 16, 23, 38, 45, 56, 72]
index = binary_search_recursive(nums, 23, 0, len(nums)-1)
print(index)  # 5

递归版看起来更“数学化”，但非递归版更节省内存（不会产生大量的函数调用栈）。通常写非递归版就够了。

新手最容易犯的错误

❌ 错误1：忘记给列表排序

二分查找的前提是有序。如果你传入一个乱序的列表，比如 [5, 2, 8, 1]，结果完全不可靠。所以用之前一定要确保排序：

nums.sort()  # 先排序再查找

❌ 错误2：边界条件写成 left < right 而不是 left <= right

如果写成 while left < right，当 left 和 right 相等时循环就结束了，但这时可能还没检查最后一个元素。例如只有一个元素的列表 [5]，要找5，left=0, right=0，循环不执行，直接返回-1，就错了。一定要用 left <= right。

❌ 错误3：更新边界时写成 left = mid 或 right = mid 而不是 mid ± 1

假如 arr[mid] 不等于 target，那么 mid 这个位置已经确认不是目标了，下一轮范围应该排除掉它。如果写成 left = mid（而不是 mid+1），当 left 和 right 只差1时，会导致死循环。例如 left=0, right=1，mid=0，如果目标在右边，更新 left=0，下一次还是同样的 left 和 right，永远跳不出去。所以一定要加1或减1。

❌ 错误4：误用浮点数除法

在计算中间位置时，必须用整数除法 //，而不是 /。因为下标必须是整数。Python 3 中 / 会返回浮点数（如 4.5），不能直接作为下标。

❌ 错误5：列表太大时 (left+right) 可能溢出

在 C++/Java 等语言中，如果 left 和 right 都很大，left+right 可能超过 int 范围。Python 中整数没有上限，所以不用担心。但为了写出跨语言的稳健代码，可以写成 mid = left + (right - left) // 2，这样能避免溢出。

完整可运行的示例程序

下面是一个完整的程序，让你可以输入一个有序列表和一个目标值，看二分查找的结果。

def binary_search(arr, target):
    """
    在有序列表arr中查找target，返回下标，未找到返回-1
    """
    left = 0                  # 左边界初始为0
    right = len(arr) - 1      # 右边界初始为数组最后一个下标

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

# 演示：用考试分数列表
scores = [55, 62, 68, 73, 78, 82, 88, 91, 95, 100]
print("考试分数列表：", scores)
find_score = 88
result = binary_search(scores, find_score)
if result != -1:
    print(f"分数{find_score}在列表中的下标是{result}（第{result+1}个）")
else:
    print(f"分数{find_score}不在列表中")

# 再试一个不存在的
find_score = 99
result = binary_search(scores, find_score)
if result != -1:
    print(f"分数{find_score}在列表中的下标是{result}")
else:
    print(f"分数{find_score}不在列表中")

运行结果：

考试分数列表： [55, 62, 68, 73, 78, 82, 88, 91, 95, 100]
分数88在列表中的下标是6（第7个）
分数99不在列表中

相关知识点

• 排序算法（如冒泡排序、快速排序）：二分查找的前提是有序，所以通常先排序（用 list.sort() 或 sorted()），然后再用二分查找。
• 二分答案（Binary Search on Answer）：不是找某一个元素，而是通过二分逼近一个最优值。例如：求一个数的平方根、在单调函数中找满足条件的最小/最大值。
• 有序数据结构的其他操作：比如在Python中，bisect 模块提供了 bisect_left 和 bisect_right 函数，可以快速找到插入位置，其实就是二分查找的变种。
• 线性查找：与二分查找对比，线性查找不需要有序，但速度慢（O(n)）。当列表很短（比如少于10个元素）时，线性查找可能更简单。

总结：二分查找是一个“快刀斩乱麻”的算法，专门对付有序的、数据量大的列表。只要记住它的步骤和边界条件，就能轻松写出正确的代码。从猜数字、查字典到找数学方程的根，它都是你的好帮手。多动手在纸上模拟几次，很快就能掌握！