搜索从一组记录中找到满足条件的数据。原书以“按给定键查找记录”为主。本章补齐独立的 Python 教材，并把线性搜索、二分搜索与字典的插入、删除放在一起讨论。
1. 键、记录和负载
一个学生记录有学号、姓名与成绩；学号可以作为键，其余字段是负载。搜索返回什么也属于接口约定：可以是下标、记录、值，或者找不到时的特殊结果。
records = [{"id": 12, "name": "小林", "score": 90},
{"id": 7, "name": "小周", "score": 80}]
本章线性搜索返回记录下标，找不到返回 −1。Python 的 data[-1] 是最后一项，不能直接把失败结果当下标使用。
2. 字典 ADT 的三个操作
插入注册记录，搜索根据键读取，删除移除记录。必须事先决定重复键是覆盖、拒绝还是保存多条；删除不存在的键时，也要定义抛异常还是返回失败。
这些规则与“用哈希还是树实现”相互独立。原书的字典概念比 Python 类型名 dict 更宽。
3. 线性搜索：逐项检查
def linear_search(records, target):
for index, row in enumerate(records):
if row["id"] == target:
return index
return -1
index = linear_search(records, 7)
if index != -1:
print(records[index]["name"]) # 小周
无需先排序。最好第一项命中，O(1)；最坏检查 n 项，O(n)。如果重复键存在，该实现返回第一次出现的位置。
4. 搜索失败也是一个正常结果
空表返回 −1；末项命中检查 n 次；不存在的键也要检查全部记录。平均成本依赖命中概率及位置分布，不能不说明假设就说总是检查 n/2 次。
5. 二分搜索的前提
记录按与搜索一致的键顺序升序排列，并能快速访问中间项。把无序列表直接交给二分搜索，可能找不到真实存在的键。
链表访问中点通常要走链接，因此不能把数组上的 O(log n) 时间结论直接搬到普通链表。
6. 闭区间二分搜索
def binary_search(records, target):
low, high = 0, len(records)-1
while low <= high:
mid = (low+high)//2
key = records[mid]["id"]
if key == target:
return mid
if key < target:
low = mid+1
else:
high = mid-1
return -1
ordered = sorted(records, key=lambda row: row["id"])
print(binary_search(ordered, 12)) # 1
每次保留可能包含目标的一半；mid 已比较过，下一轮应排除它。停止时 low > high，候选区间为空。最好 O(1)，最坏 O(log n)，额外空间 O(1)。
7. 重复键与 lower_bound
普通二分命中时立即返回，不保证返回第一个重复项。若需要插入位置或第一次出现，可以找“首个键不小于 target”的位置：
def lower_bound(records, target):
low, high = 0, len(records) # 半开区间
while low < high:
mid = (low+high)//2
if records[mid]["id"] < target:
low = mid+1
else:
high = mid
return low
返回值可能为 len(records)，表示应插入末尾，不表示命中。要确认存在，还需检查索引在范围内且键相等。
8. 搜索快，不等于更新也快
def insert_ordered(records, row):
pos = lower_bound(records, row["id"])
if pos < len(records) and records[pos]["id"] == row["id"]:
records[pos] = row # 本例重复键覆盖
else:
records.insert(pos, row)
return pos
找位置 O(log n)，列表中间插入仍要移动后项，最坏 O(n)。从有序数组删除也可能移动 O(n) 项。不要只计算查找位置的部分。
9. 未排序表与有序表的成本
| 操作 | 未排序列表 | 有序列表 |
|---|---|---|
| 按键搜索 | 最坏 O(n) | 最坏 O(log n) |
| 直接末尾追加，不检查重复 | 摊销 O(1) | 只有保持顺序时才可这样做 |
| 按键插入/覆盖，先确认键 | 最坏 O(n) | 最坏 O(n) |
| 按键删除，保留相对顺序 | 最坏 O(n) | 最坏 O(n) |
原书未排序表插入的 O(1) 是不先检查重复键、允许末尾追加的模型。如果必须搜索旧键再覆盖，完整操作就不是 O(1)。
10. Python dict 的接口示例
by_id = {12: {"name": "小林", "score": 90}}
by_id[7] = {"name": "小周", "score": 80}
print(by_id.get(7))
removed = by_id.pop(12, None)
在常规假设下，哈希字典按键操作平均 O(1)，最坏可以 O(n)。dict 的迭代顺序是插入顺序，不是按键大小排序；范围查询并非它的天然强项。
11. 选择方法时把准备成本算进去
一次查询：线性扫描可能最省事。大量重复查询：预排序后二分、建立哈希索引都可能值得。频繁按键增删又要有序范围查询：平衡搜索树更适合讨论。
对 n 条记录先排序需 O(n log n)，随后 q 次二分需 O(q log n)；总量不能只写最后一次查询的 O(log n)。
12. 边界与测试清单
assert linear_search([], 7) == -1
assert binary_search([], 7) == -1
assert binary_search([{"id": 7}], 7) == 0
assert binary_search([{"id": 7}], 8) == -1
assert lower_bound([{"id": 1}, {"id": 3}, {"id": 3}], 3) == 1
assert lower_bound([{"id": 1}], 9) == 1
检查空表、首末命中、失败、重复键、插入首末位置和删除后的顺序。下一章将深入哈希法，随后是 BST 与平衡树。