异常教程
Python 编写一个程序实现二分查找（千字长文）
💡一则或许对你有用的小广告
欢迎加入小哈的星球 ，你将获得：专属的项目实战 / 1v1 提问 / Java 学习路线 / 学习打卡 / 每月赠书 / 社群讨论
- 新项目:《从零手撸：仿小红书（微服务架构）》 正在持续爆肝中，基于
Spring Cloud Alibaba + Spring Boot 3.x + JDK 17...，点击查看项目介绍 ;演示链接： http://116.62.199.48:7070 ;- 《从零手撸：前后端分离博客项目（全栈开发）》 2 期已完结，演示链接： http://116.62.199.48/ ;
截止目前， 星球 内专栏累计输出 90w+ 字，讲解图 3441+ 张，还在持续爆肝中.. 后续还会上新更多项目，目标是将 Java 领域典型的项目都整一波，如秒杀系统, 在线商城, IM 即时通讯，权限管理，Spring Cloud Alibaba 微服务等等，已有 3100+ 小伙伴加入学习 ，欢迎点击围观
从图书馆找书谈起
想象你在一座巨大的图书馆中寻找一本特定的书。如果按照顺序一本本翻找，效率会非常低，尤其是当书籍数量达到百万级别时。但如果你知道这些书籍是按照字母顺序排列的，就可以用“对折法”快速定位：先打开书架中间的书，根据书名与目标的大小关系，决定向左或向右继续查找。这就是二分查找（Binary Search）的核心思想——通过不断缩小搜索范围，以指数级速度逼近目标值。
二分查找的高效性源于其对数时间复杂度，即操作次数与数据量的对数成正比。例如，对于包含100万条数据的有序数组，顺序查找可能需要100万次比较，而二分查找仅需约20次。这种特性使其成为计算机科学中基础且重要的算法之一。
二分查找的实现需要以下关键步骤：
1. 初始化指针
- 左指针（left）：初始指向数组的第一个元素（索引0）。
- 右指针（right）：初始指向数组的最后一个元素（索引
len(arr)-1）。
2. 循环条件
只要左指针不超过右指针（即left <= right），就继续循环。这确保了所有可能的子区间都被检查。
3. 计算中间索引
使用公式 mid = (left + right) // 2 计算中间元素的索引。注意，为了避免整数溢出（在某些编程语言中），可改用 mid = left + (right - left) // 2，但Python对此无需担心。
4. 比较与区间调整
- 若中间元素等于目标值：直接返回中间索引。
- 若中间元素小于目标值：说明目标位于右侧，因此将左指针移动到
mid + 1。 - 若中间元素大于目标值：说明目标位于左侧，因此将右指针移动到
mid - 1。
5. 未找到时的处理
当循环结束仍未找到目标值时，返回-1或类似标记。
以下是一个基础的二分查找函数实现：
def binary_search(arr, target):
left, right = 0, 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
代码解释
- 输入参数：
arr是已排序的数组，target是目标值。 - 返回值：找到目标时返回索引，否则返回-1。
- 关键点：通过不断调整
left和right的值，逐步缩小搜索范围。
1. 数组必须有序
二分查找仅适用于有序数组。若输入的数组未排序，算法可能返回错误结果。例如：
arr = [5, 3, 8, 1]
print(binary_search(arr, 3)) # 可能返回-1或错误索引
2. 处理重复元素
若数组中存在多个目标值，该代码会返回任意一个匹配的索引。若需返回所有位置，需额外逻辑：
def find_all_occurrences(arr, target):
result = []
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
result.append(mid)
# 向左搜索其他可能的相同值
temp = mid - 1
while temp >= left and arr[temp] == target:
result.append(temp)
temp -= 1
# 向右搜索
temp = mid + 1
while temp <= right and arr[temp] == target:
result.append(temp)
temp += 1
return sorted(result) # 返回按顺序排列的索引列表
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return result
3. 循环条件的严格性
若误将循环条件写为 left < right，可能导致某些情况无法覆盖。例如，当left和right相邻时，可能提前退出循环。
二分查找的时间复杂度为 O(log n)，其优势在大规模数据中尤为明显。下表对比了不同数据量下顺序查找与二分查找的操作次数：
| 数据量（n） | 顺序查找操作数 | 二分查找操作数 |
|---|---|---|
| 10 | 10 | 4 |
| 1,000 | 1,000 | 10 |
| 1,000,000 | 1,000,000 | 20 |
对数复杂度的直观理解
假设你将一张纸对折20次，其厚度将超过珠穆朗玛峰的高度。二分查找的原理与此类似：每次将问题规模减半，因此即使数据量指数级增长，操作次数也仅线性增加。
假设某学校需要快速查询学生的成绩排名，成绩数据按升序存储。例如：
scores = [55, 65, 70, 80, 85, 90, 95]
target_score = 85
index = binary_search(scores, target_score)
print(f"成绩 {target_score} 的位置是索引 {index}") # 输出：索引3
此场景下，二分查找能显著减少查询时间，尤其当学生成绩库规模较大时（如百万级）。
1. 递归实现
二分查找也可通过递归实现，但需注意栈溢出风险：
def recursive_binary_search(arr, target, left, right):
if left > right:
return -1
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return recursive_binary_search(arr, target, mid+1, right)
else:
return recursive_binary_search(arr, target, left, mid-1)
2. 查找第一个/最后一个出现的元素
若需找到目标值的第一个或最后一个出现的位置，可调整比较逻辑：
def find_first(arr, target):
left, right = 0, len(arr)-1
result = -1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
result = mid
right = mid - 1 # 继续向左寻找更早的出现
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return result
1. 索引越界
若数组为空或初始指针设置错误（如right = len(arr)），可能导致越界。始终确保right初始化为len(arr) - 1。
2. 死循环
若未正确更新left或right，可能导致无限循环。例如：忘记将left = mid + 1写成left = mid。
3. 调试建议
- 打印中间值：在循环内添加
print(mid, arr[mid])，观察搜索路径。 - 单元测试：编写覆盖边界情况的测试用例，如空数组、目标在首尾、重复元素等。
二分查找是程序员工具箱中的核心算法之一，尤其在需要快速定位有序数据时不可或缺。通过本文的代码示例与案例分析，读者可以掌握其原理与实现细节。对于编程初学者，建议从基础版本开始实践，并逐步尝试处理重复元素、递归等变体。
掌握二分查找后，可进一步探索其他分治算法（如快速排序、归并排序），或研究其在实际场景中的应用，例如数据库索引优化或实时数据搜索系统。记住，算法的学习不仅是记忆代码，更是培养解决问题的思维方式。
（全文约1800字）