07 什么是搜索？
记录与键、线性、二分和更新成本
第 01 题 问题 1
一条学生记录的学号、姓名、成绩中，哪个可以作为搜索键？
参考答案
可按业务选择，例如学号。
解析
键是用来定位记录的字段，其他字段仍随完整记录关联。
第 02 题 问题 2
搜索返回 −1 后直接访问 records[-1]，有什么问题？
参考答案
会读取末项，而不是表示失败。
解析
Python 支持负下标，必须先检查失败标记。
第 03 题 问题 3
线性搜索对无序表可直接执行吗？
参考答案
可以。
解析
它逐项比键，不要求预先排序。
第 04 题 问题 4
线性搜索有重复键时，本章实现返回哪个位置？
参考答案
第一次出现的位置。
解析
遇到相等立即返回；若需全部匹配要继续扫描并收集。
第 05 题 问题 5
对无序列表执行二分搜索，结果有保证吗？
参考答案
没有。
解析
淘汰一半范围依赖键顺序与搜索比较规则一致。
第 06 题 问题 6
有序数组 [1,4,7,12,18,25,31,40] 搜索 25，闭区间访问哪些下标？
参考答案
先 3，再 5，返回 5。
解析
首次 mid=3 的 12 较小，low=4；随后 mid=5 命中。
第 07 题 问题 7
普通二分命中重复键后，保证找到第一个吗？
参考答案
不保证。
解析
立即返回某个中点；找首个位置可使用 lower_bound。
第 08 题 问题 8
lower_bound([1,3,3],3) 与 lower_bound([1,3,3],4) 返回什么？
参考答案
分别为 1、3。
解析
求首个不小于目标的位置；3 是末尾插入位置，不表示命中。
第 09 题 问题 9
有序列表找插入位置 O(log n)，完整插入也是 O(log n) 吗？
参考答案
一般不是，最坏 O(n)。
解析
中间插入仍需移动后续引用；查找和移动要相加。
第 10 题 问题 10
未排序列表直接追加摊销 O(1)，若要求重复键覆盖还可这样写吗？
参考答案
不能直接断言 O(1)。
解析
要先查已有键，完整操作可能 O(n)。
第 11 题 问题 11
建立排序表后进行 q 次二分查询，总成本如何写？
参考答案
O(n log n + q log n)。
解析
包含预排序与全部查询，不能只写最后一次查询的成本。
第 12 题 问题 12
dict 的迭代顺序等于按键大小升序吗？
参考答案
不是，是插入顺序。
解析
哈希查找快不代表天然支持有序范围查询。