二分查找：像猜数字一样快速找到目标

二分查找是一种在有序列表中快速找到某个值的算法。它的核心思想是：每次把查找范围对半缩小，通过比较中间元素和目标值，决定目标在左半边还是右半边，直到找到或确定不存在。就像玩猜数字游戏，每次猜中间的数，很快就能锁定答案。二分查找的速度非常快，适合处理大量有序数据。

为什么需要二分查找？

假设你有100个按学号排好的同学名单，想找学号20102的同学。如果一个个从开头找（线性查找），最坏情况要查100次。如果用二分查找，最多查7次（因为100<2^7=128）。数据量越大，二分查找的优势越明显——1万条数据最多只需14次，百万条也只需20次左右。它的时间效率用O(log n)表示，而线性查找是O(n)。

二分查找的生活场景

查字典：你要查“猫”字。字典是按拼音排序的，你不会从第一页翻，而是直接翻到中间，看中间的字是“L”还是“M”？如果“M”排在“L”后面，而“猫”是M开头的，你就知道目标在后半本。再在后半本中间翻，很快就能找到。

猜价格游戏：电视上猜商品价格，主持人说“高了”或“低了”。如果你每次都猜中间价（比如1~1000元，猜500），就能用最少次数猜中。这就是二分查找的实战。

按成绩找排名：班里成绩单按分数从低到高排序。你想知道某个分数（比如85分）排在第几位？二分查找能快速定位。

二分查找的步骤详解

假设有一个已排序的列表，比如 [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]，我们要找23。

1. 设定范围：左边界 left = 0（第一个元素索引），右边界 right = 9（最后一个元素索引）。
2. 取中间：中间索引 mid = (0+9)//2 = 4，对应元素 16。
3. 比较：16 < 23，说明目标在右半部分。所以把左边界移动到 mid+1 = 5，右边界不变（9）。
4. 重复：现在范围是索引5~9，中间索引 (5+9)//2 = 7，对应元素 56。56 > 23，所以目标在左半部分，右边界变为 mid-1 = 6。
5. 继续：范围索引5~6，中间 (5+6)//2 = 5，对应元素 23，相等！返回索引5。

每次比较都让范围减半，很快就能找到。

代码实现（一步一步来）

下面是一个完整的二分查找函数，包含详细注释。

def binary_search(arr, target):
    """
    在有序列表 arr 中查找目标值 target，返回索引，没找到返回 -1
    """
    left = 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          # 移动左边界到中间+1
        else:                       # 目标在左边
            right = mid - 1         # 移动右边界到中间-1

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

# 测试代码
numbers = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]   # 有序列表
target = 23                                        # 要找到的值
index = binary_search(numbers, target)
if index != -1:
    print(f"找到了！{target} 在索引 {index} 位置。")
else:
    print(f"未找到 {target}。")

输出：

找到了！23 在索引 5 位置。

代码中的关键细节

• left 和 right：代表当前搜索范围的起止索引。初始时覆盖整个列表。
• while left <= right：循环条件。当 left 等于 right 时，范围里还有一个元素，要继续检查。如果写成 left < right，会漏掉最后一个元素。
• mid = (left + right) // 2：求中间索引。// 是整数除法，保证结果是整数。如果列表很长，可以写成 mid = left + (right - left) // 2 来避免整数溢出（Python 中整数无限大，但其他语言需要注意）。
• 更新边界：如果 arr[mid] < target，说明目标在右侧，所以左边界变成 mid+1（因为 mid 已经比较过，不需要再包含）。同理，如果目标在左侧，右边界变成 mid-1。
• 返回值：找到返回索引，没找到返回 -1（常见约定）。

新手常犯的错误

1. 列表没有排序：二分查找的前提是列表必须有序（通常从小到大）。如果对无序列表查找，结果完全错误。解决方法：先排序，再二分。
2. 边界条件搞错：比如循环条件写成 left < right，会导致当搜索范围只剩一个元素时直接退出，可能漏掉目标。一定要用 left <= right。
3. mid 计算错误：忘记用整数除法，导致 mid 是小数，无法用作索引。Python 中 // 确保整数。
4. 更新边界时忘记 +1 或 -1：比如 left = mid 而不是 mid+1，可能导致死循环，因为 mid 可能一直等于 left，范围不缩小。记住：比较过的中间元素要排除。

完整示例：从用户输入查找成绩

下面是一个完整的程序，用户输入一个分数，程序在提前排好序的成绩列表中查找，并告诉用户是否找到以及排名（索引+1）。

# 假设全班成绩已经按从低到高排序
scores = [62, 68, 73, 78, 82, 85, 88, 92, 95, 98]   # 有序列表，学号按成绩排

def binary_search(arr, target):
    left = 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

# 让用户输入要查找的分数
user_input = input("请输入要查找的分数（整数）：")
target_score = int(user_input)    # 将字符串转换为整数

index = binary_search(scores, target_score)
if index != -1:
    print(f"找到分数 {target_score}，排名第 {index+1} 名（索引 {index}）。")
else:
    print(f"没有找到分数 {target_score}。")

运行示例：

请输入要查找的分数（整数）：85
找到分数 85，排名第 6 名（索引 5）。

二分查找的变形（拓展）

除了找精确值，二分查找还能用于：

• 找第一个大于等于目标的位置（下界）
• 找最后一个小于等于目标的位置（上界）
• 在旋转数组（先升后降）中找最小值

这些变形只是调整比较和边界更新的逻辑，核心思想不变。

与线性查找对比

当列表有序且长度超过几十时，二分查找优势明显。

相关知识点指引

• 排序算法：二分查找前需要排序。可以学习冒泡排序、快速排序、归并排序等。
• 递归实现：二分查找也能用递归写，逻辑更清晰（但可能效率略低）。
• 数据结构：二叉搜索树（BST）就是基于二分思想构建的树状数据结构，查找同样高效。
• 时间复杂度：O(log n) 的数学含义，以及对数运算。

总结：二分查找就像玩“猜中间”的游戏，每次排除一半可能性，快速逼近答案。记住前提：数据必须有序。下次找东西时，试试用二分的思想——先猜中间，再根据反馈缩小范围，你会发现自己也能像计算机一样高效思考！