---
title: "07-查找"
created: 2026-08-29
tags:
  - 基础与理论
  - 数据结构
  - "408"
---

# 07 查找

> 📚 本文是 [[00-数据结构总览|数据结构]] 的第 7 篇，相关系列见 [[00-基础与理论|基础与理论]]。

查找 = 在数据集合里找满足条件的数据。衡量它的尺子是 **ASL（平均查找长度）**——找一趟平均要比几次。本章一条主线：**怎么让每次比较"丢掉"更多无效数据**——折半丢一半、BST 按大小分家、B 树一层丢一批、散列直接一步到位。

## 一、ASL：查找的度量衡

$$ASL = \sum_{i=1}^{n} p_i \cdot c_i \quad (p_i 查第 i 个的概率, \ c_i 比较次数)$$

- 通常等概率 p = 1/n
- **ASL 成功 / ASL 失败**两个口径，408 大题两个都要求算

## 二、顺序与折半查找

### 顺序查找：O(n)，毫无门槛

ASL 成功 = (n+1)/2。对**链表也适用**（顺序存储非必需）。优化：有序表顺序查找失败时可以提前终止——失败 ASL 会降。

### 折半查找：O(log n)，只吃有序顺序表

```
low=1, high=n
while low <= high:
    mid = (low + high) / 2    # 向下取整
    if key == a[mid]: 找到
    elif key < a[mid]: high = mid − 1
    else: low = mid + 1
```

**手算例题**：有序表 {7, 14, 18, 21, 23, 29, 31, 35, 38, 42, 46}（11 个），找 42：

1. mid=6 → a[6]=29 < 42 → low=7
2. mid=9 → a[9]=38 < 42 → low=10
3. mid=10 → a[10]=42 ✅ **3 次比较**

**判定树（408 大题）**：把每次 mid 画成树——

- **判定树是平衡的 BST 形状**：n 个元素，树高 = ⌈log₂(n+1)⌉
- **ASL 成功** = 各层结点 × 层号之和 ÷ n。11 个结点的判定树：第 1 层 1 个、第 2 层 2 个、第 3 层 4 个、第 4 层 4 个
  ASL = (1×1 + 2×2 + 3×4 + 4×4) / 11 = 33/11 = **3** ✅
- ASL 失败 = 到达 n+1 个失败结点（外部结点）的平均深度
- ⚠️ 折半查找**必须顺序存储**（要随机访问 mid）——链表不能折半

## 三、二叉排序树（BST）与平衡的执念（AVL）

### BST：左小右大

- 定义：左子树所有结点 < 根 < 右子树所有结点（递归成立）
- **中序遍历得升序序列**——判 BST 的标准手段
- 查找/插入 O(h)；**删除**三情形：叶子直接删；单孩子连上去；**双孩子用"中序前驱（左子树最右）或中序后继（右子树最左）"顶替再删那个顶替者**
- ⚠️ 致命伤：**有序输入插入 → 退化成单斜树，O(n)**——n=1000 时查找从 ~10 次变 1000 次

### AVL：旋转的艺术

任何结点**左右子树高度差 |bf| ≤ 1** 的 BST。插入破坏平衡 → 找**离插入点最近的失衡结点**，四招旋转：

| 情形 | 判断（LL/LR/RL/RR） | 处理 |
|---|---|---|
| LL | 插在左孩子的左子树 | **右单旋** |
| RR | 插在右孩子的右子树 | **左单旋** |
| LR | 插在左孩子的右子树 | **先左旋左孩子，再右旋自己** |
| RL | 插在右孩子的左子树 | **先右旋右孩子，再左旋自己** |

💡 记忆：**平衡因子符号连写就是操作名**（LL=右旋、LR=左右双旋…）。旋转后子树高度恢复插入前，**不需要向上继续调整**（这是 AVL 插入的性质；删除则可能向上传播）。

- 手算：依次插入 {50, 30, 70, 20, 40, 35}——插 35 后 50 的 bf=2 且路径 50→30→40 是 LR → 对 50 先左旋 30 再右旋 50，40 升为子树根
- 复杂度：O(log n) 有保证；代价是插入删除的旋转开销——**AVL 适合查多改少，改多场景 B 树更省**

## 四、B 树与 B+ 树：磁盘时代的王者

**为什么需要 B 树**：红黑/AVL 二叉分叉，树高 log₂n——在磁盘上就是 log₂n 次 I/O；磁盘一次 I/O ≈ 0.1ms，太贵。**把树的"一结点多孩子"对准"磁盘一块多数据"**，层高压到 3~4 层。

### B 树（多路平衡查找树，m 阶）

- 每结点最多 **m 棵子树、m−1 个关键字**；根结点至少 2 棵子树；**非根非叶至少 ⌈m/2⌉ 棵子树**
- 所有叶子在同一层（绝对平衡）；结点内关键字**有序**，多路分支
- 查找：结点内（顺序/折半）+ 沿途下坠，**最多比 h 次 × 结点内比较**

### B+ 树（数据库索引的标准答案）

| 维度 | B 树 | B+ 树 |
|---|---|---|
| 数据存放 | **所有结点**都存关键字和数据 | **只有叶子**存数据，内部结点只放索引 |
| 叶子结点 | 不相连 | **链表串起来** → 范围查询/顺序遍历起飞 |
| 查找稳定性 | 可能到根（时快时慢） | **必到叶子**（每次代价一致） |
| 单结点容纳 | 少（存了数据） | 多（只有键）→ 树更矮 → I/O 更少 |
| 典型应用 | 文件系统（NTFS） | **MySQL InnoDB** |

💡 InnoDB 默认树高 3 层可扛 ~2000 万行——每层一个页（16KB），3 次 I/O 定位任意一行。

## 五、散列（Hash）：一步直达的极致

### 基本盘

- **散列函数 Hash(key) → 存储地址**：理想 O(1)，冲突（不同 key 映射同址）不可避免——**鸽巢原理**（key 域 > 表长时必冲突）
- 常用构造法：
  - **除留余数**：`H(key) = key % p`，**p 取 ≤ 表长的最大素数**（408 铁律）
  - 直接定址 H(k)=k 或 a·k+b（无冲突但要 key 分布知道）
  - 平方取中、折叠（了解）

### 冲突处理两家族

**开放定址法**（冲突了就在表内另找位置，**物理删除是禁忌**——要打删除标记）：

| 方法 | 探测序列 | 问题 |
|---|---|---|
| 线性探测 | d, d+1, d+2, …（模 m） | **堆积（聚集）**：连续占用越滚越长 |
| 平方探测 | d, d+1², d−1², d+2², … | 缓解堆积；**m 必须是 4k+3 型素数**才能探遍全表 |
| 双散列 | d + i×H₂(key) | 最好；多算一个散列函数 |

**拉链法（链地址法）**：同址的挂链表——无堆积、删随便，但指针开销；**装填因子 α = 元素数/表长**，α 越大 ASL 越大。

### ASL 计算（408 大题必考套路）

**手算例题**：H(key)=key%7，散列表长 7，线性探测，依次插入 {15, 22, 29, 36}：

- 15%7=1 → 放 1 号；22%7=1 冲突 → 探 2 号；29%7=1 冲突 → 探 2、3 号；36%7=1 → 探 2、3、4 号
- 表：`[_, 15, 22, 29, 36, _, _]`
- **ASL 成功** = (1+2+3+4)/4 = **2.5**
- **ASL 失败**：散列到 0 号要探 5 次（0→1→2→3→4→5 空停？注意失败判定要探到**空位**为止；0 号散列的 key 候选 7,14,21… 从 0 号开始探到 5 号空 = 5 次）——逐散列地址统计**到下一个空位**的距离再平均：0 号 5 次、1 号 4 次、2 号 3 次、3 号 2 次、4 号 1 次、5 号 1 次、6 号 1 次 → (5+4+3+2+1+1+1)/7 = **17/7 ≈ 2.43**

⚠️ 失败 ASL 的分母是**散列函数的取值个数 p**（不是表长，也不算装填元素数）——最阴的坑，务必看清题目统计口径。

## 六、各结构查找全家福

| 结构 | 平均 | 最坏 | 备注 |
|---|---|---|---|
| 顺序 | O(n) | O(n) | 无序可用、链表可用 |
| 折半 | O(log n) | O(log n) | 要有序 + 顺序存储 |
| BST | O(log n) | **O(n)**（退化） | 动态、实现简单 |
| AVL | O(log n) | O(log n) | 旋转维护平衡 |
| B/B+ 树 | O(log n) 树高极低 | O(log n) | 磁盘/数据库 |
| 散列 | **O(1)** | O(n) | 无序、不支持范围查询 |

## 七、盲点自测

1. 折半查找为什么不能链表？（mid 需要随机访问）
2. 11 个元素折半查找判定树第 4 层几个结点？（4 个）
3. BST 删除双孩子结点用什么顶替？（中序前驱/后继）
4. AVL 插入 LR 型怎么旋？（先左旋左孩子再右旋失衡点）
5. B+ 树为什么比 B 树更受数据库欢迎？（叶子链表利于范围查询、内结点纯索引更矮、查找代价稳定）
6. 除留余数法的 p 怎么选？（≤ 表长的最大素数）
7. 线性探测为什么不许物理删除？（会截断探测链，后面的同义词找不到——打标记软删除）
8. 失败 ASL 的分母是谁？（散列函数地址空间大小 p）

## 八、动手玩

```python
# 线性探测散列表：把本文例题跑一遍
def insert_hash(table, key):
    m = len(table)
    d = key % 7
    while table[d] is not None:      # 冲突则线性探测
        d = (d + 1) % m
    table[d] = key

def asl_success(table, keys):
    m, total = len(table), 0
    for k in keys:
        d, cnt = k % 7, 1
        while table[d] != k:
            d, cnt = (d + 1) % m, cnt + 1
        total += cnt
    return total / len(keys)

t = [None] * 7
for k in (15, 22, 29, 36):
    insert_hash(t, k)
print(t)                             # [None, 15, 22, 29, 36, None, None]
print(asl_success(t, [15, 22, 29, 36]))   # 2.5，与手算一致
```

## 参考资料

- 王道《数据结构考研复习指导》第 7 章
- 《MySQL 是怎样运行的》——B+ 树在 InnoDB 里的落地细节（儿童版数据库内核书，极佳）
- [[09-磁盘与固态硬盘]]——为什么磁盘时代树要"矮胖"：I/O 代价模型
- [[00-刷题理模型|刷题理模型]]——哈希题单（两数之和、字母异位词分组）

⬅️ [[06-图|图]] 🏠 [[00-基础与理论|00-基础与理论]] ➡️ [[08-排序|排序]]