回顾线性搜索
描述首次匹配算法。在包含 1,000 个值的列表中查找不存在的目标，可能需要多少次比较？
B2.4 · 搜索 · 已学习
二分搜索
利用有序数据，在每一步排除一半剩余候选项。
本节课资源
观看二分搜索
目标值 42有序数值 · 下方显示索引8 个候选项
剩余候选项已排除正在检查
从全部八个值开始。计算中间索引时向下取整，再检查该位置的值。
low = 0mid = —high = 7Python 实现
高亮 = 刚执行的语句。跳过的分支不会高亮。
def binary_search(items, target): low = 0 high = len(items) - 1 while low <= high: mid = (low + high) // 2 if items[mid] == target: return mid elif items[mid] < target: low = mid + 1 else: high = mid - 1 return -1准备调用 binary_search(items, 42)。
已检查 0 个值
学完本节课后
- 解释二分搜索为什么要求输入有序。
- 在成功与失败的搜索中跟踪 low、mid 和 high。
- 实现二分搜索，并测试其边界。
复习课程
找到中间位置
手工在 [3, 8, 12, 17, 23, 31, 42, 56] 中搜索 31。使用从零开始的索引、low = 0、high = len(items) - 1 和 mid = (low + high) // 2。比较未匹配后，解释可以舍弃哪一半。
跟踪两次搜索
建立表格，包含迭代次数、low、high、mid、items[mid] 与下一步操作。跟踪成功查找 31 和失败查找 20 的过程。记录每种情况循环终止的原因。
实现与测试
编写 binary_search(items, target)，返回匹配索引或 -1。在 low <= high 时继续。测试空列表、单元素列表、首尾值及不存在的值。比较预期与实际结果。
解释你的决策
解释为什么下一边界是 mid + 1 或 mid - 1，而不是 mid。说明有重复值时能保证什么。
下课前
离堂问题
是什么使搜索区间不断缩小？为什么无序输入会破坏这一推理？
本主题作业
周末作业：第 1、2 题与阅读
完成算法讲义第 1、2 题，再阅读教材的二分搜索部分。请在 9 月 21 日星期一前准备好作业。