查找
🎯 一句话秒杀：查找就是在一堆数据中找到目标——顺序查找最笨但通用，折半查找快但要求有序，哈希查找最快但占空间。
① 📊【历年真题考情】
本章（查找）在广东专升本计算机统考中的位置：
| 项目 | 结论 |
|---|---|
| 出题频次 | ⭐⭐⭐⭐——2026 考纲全解标注"查找：单选、填空、计算，约10分"；折半查找 3/4 年（2021/2023/2024/2026 全考） |
| 常考题型 | 单选（2021 单选12/13、2023 单选17、2024 单选13、2026 单选15）、计算（折半过程） |
| 预估分值 | 5~15 分 / 200 分（约 3%~8%） |
| 考纲归属 | 2026 考纲「算法」考点17（顺序/折半查找、哈希） |
考场真实出现过的高频题：
- 2021 单选12：哈希
H(k)=k%9，表 {3,12,24,46,10,20}，散列地址为 0 的元素个数 → 0 - 2021 单选13：适用于折半查找的是 → 顺序有序
- 2023 单选17：二分查找前提 → 键值有序顺序表
- 2024 单选13：折半查找 {12,18,21,35,45,55,66} 找 21 → 3 次
- 2026 单选15：折半查找平均时间复杂度 → O(log n)
🎯 学习目标：学完本章，你能 ① 手推折半查找的 mid 过程并数出比较次数；② 用哈希函数逐元素算地址；③ 判断什么场景用哪种查找；④ 说出各算法复杂度——这四类题就是本章真题的全部考法。
② 🗣️【零基础大白话引入】
查找是什么？ 查找就是"在一堆数据里找目标"。想象你在图书馆找一本书，有三种找法：
- 顺序查找 = 从第一排书架一本一本翻，直到找到——最笨，但任何书架都能用
- 折半查找 = 字典按拼音排好了，翻到中间看"目标在左边还是右边"，每次都排除一半——快，但必须排好序
- 哈希查找 = 每本书按编号直接放固定柜子，报编号直奔柜子——最快，但要提前规划好"编号→柜子"的规则
为什么学这个？ 考试就考三件事：① 给你有序表，你手推折半查找要比较几次；② 给你哈希函数，你算每个元素放哪；③ 问你哪个查找方法什么时候用。全是套路题，学会推演就能拿分。
💡 本章主线：顺序（O(n) 慢）→ 折半（O(log n) 快但有序）→ 哈希（O(1) 最快但占空间）。越快的查找，限制条件越多——这是全章逻辑。
③ 📖【正式核心知识点讲解】
本章知识点 = 考纲要求 + 历年真题实际考过的内容。真题未考、考纲不作要求的超纲内容已剔除或标注"了解"。
3.1 基本概念
| 术语 | 定义 |
|---|---|
| 查找 | 在数据集合中找出满足条件的元素 |
| 关键字 | 唯一标识一个记录的数据项（如学号） |
| 平均查找长度 ASL | 所有查找操作的比较次数之和 / 元素个数 |
ASL = Σ(概率 × 比较次数) 查找算法的核心指标就是 ASL
3.2 顺序查找
int SeqSearch(int arr[], int n, int key) {
for (int i = 0; i < n; i++)
if (arr[i] == key) return i; // 返回下标
return -1; // 没找到
}性能分析：
- 查找成功平均：ASL = (n+1)/2 ≈ O(n)
- 查找失败：n 次比较
- 优点： 对数据无要求（有序无序都行）
- 缺点： 慢
💡 顺序查找 ASL 代入：n=10 时 ASL=(10+1)/2=5.5（平均比较 5.5 次）。
3.3 折半查找（二分查找）⭐
前提：数据必须有序！且必须顺序存储（数组）
int BinarySearch(int arr[], int n, int key) {
int low = 0, high = n - 1;
while (low <= high) {
int mid = (low + high) / 2; // 或 low + (high-low)/2
if (arr[mid] == key) return mid;
else if (arr[mid] < key) low = mid + 1; // 去右半
else high = mid - 1; // 去左半
}
return -1; // 没找到
}3.3.1 折半查找的适用条件（2021 单选13 / 2023 单选17 必考）
| 存储结构 | 有序 | 能否折半 |
|---|---|---|
| 顺序存储（数组） | 有序 | ✅ 可以 |
| 顺序存储 | 无序 | ❌ 不可以（需先排序） |
| 链式存储（链表） | 有序 | ❌ 不可以（无法随机访问中间元素） |
| 链式存储 | 无序 | ❌ 不可以 |
✅ 2021 单选13：适用于折半查找的是 → D. 顺序有序 ✅ 2023 单选17：二分查找 → 键值有序顺序表 🚨 关键：链表不能折半——因为折半要
mid=(low+high)/2直接跳到中间，链表只能从头遍历，做不到随机访问！
3.3.2 折半查找比较次数（2024 单选13 必考 · 表格化推演）
真题：通过折半查找对关键字序列 {12, 18, 21, 35, 45, 55, 66}，查找 21 需要查找（ ）次
| 步骤 | low | high | mid=(low+high)/2 | arr[mid] | 比较结果 | 操作 |
|---|---|---|---|---|---|---|
| 1 | 0 | 6 | 3 | 35 | 21 < 35 | high = mid-1 = 2（去左半） |
| 2 | 0 | 2 | 1 | 18 | 21 > 18 | low = mid+1 = 2（去右半） |
| 3 | 2 | 2 | 2 | 21 | 21 == 21 | 找到！ |
✅ 答案：共 3 次（A.4 B.3 C.2 D.1 → 选 B） 记忆：每次比较排除一半，7 个元素最多 log₂7≈3 次。
3.3.3 折半查找的时间复杂度（2026 单选15 必考）
每次比较排除一半区间，比较次数与 log₂n 同阶 → O(log n)
| 选项 | 判断 |
|---|---|
| A. O(1) | ❌ 那是哈希理想情况 |
| B. O(log n) | ✅ 正确 |
| C. O(n) | ❌ 那是顺序查找 |
| D. O(n log n) | ❌ 那是部分排序算法 |
✅ 2026 单选15：对长度为 n 的有序表折半查找，平均时间复杂度 → B. O(log n) 前提：表有序 + 随机访问（数组）。
3.4 分块查找
介于顺序查找和折半查找之间
思想：
- 数据分成若干块，块内无序，块间有序
- 建立索引表（每块最大关键字+起始位置）
- 先在索引表二分查找 → 再到块内顺序查找
ASL = 索引表查找 + 块内查找
💡 分块查找 = 折半（索引表）+ 顺序（块内）的混合体。块间有序才能用索引表折半。
3.5 哈希查找（散列查找）⭐
哈希表
通过哈希函数直接计算出数据存储位置——理想情况下 O(1)！
常用哈希函数
| 方法 | 做法 | 适用场景 |
|---|---|---|
| 除留余数法 | key % p（p为质数） | 最常用（真题考这个） |
| 直接定址法 | key 或 key+a | 关键字分布连续 |
| 数字分析法 | 取关键字中分布均匀的几位 | 关键字位数多 |
| 平方取中法 | key²取中间位 | 关键字位少 |
// 除留余数法是最常用的哈希函数
int hash(int key) {
return key % 11; // p=11（质数）
}3.5.1 哈希地址逐元素计算（2021 单选12 必考）
真题：表 {3, 12, 24, 46, 10, 20}，H(k)=k%9，散列地址为 0 的元素个数是（ ）
逐元素推演：
| 关键字 k | k % 9 | 散列地址 |
|---|---|---|
| 3 | 3 % 9 | 3 |
| 12 | 12 % 9 | 3 |
| 24 | 24 % 9 | 6 |
| 46 | 46 % 9 | 1 |
| 10 | 10 % 9 | 1 |
| 20 | 20 % 9 | 2 |
余数序列：3, 3, 6, 1, 1, 2 → 没有元素的地址是 0 → 个数 = 0 ✅ 答案：地址 0 的元素个数为 0（2021 单选12） 注意：3 和 12 都映射到地址 3 → 产生冲突（这正是哈希冲突的实例）
3.5.2 冲突处理
冲突： 不同关键字映射到同一位置
| 处理方法 | 做法 | 特点 |
|---|---|---|
| 开放定址法 | 冲突了就往后找空位 | 线性探测、平方探测 |
| 链地址法 | 同一位置的元素连成链表 | 查找/插入方便 |
线性探测法： Hi = (H(key) + di) % m，其中 di = 1,2,3,...
线性探测代入示例：表长 m=7，H(k)=k%7，依次插入 50, 12, 26：
- 50：
50%7=1→ 位置 1 空 → 放 [1]=50 - 12：
12%7=5→ 位置 5 空 → 放 [5]=12 - 26：
26%7=5→ 冲突！ 位置 5 已占 → 线性探测(5+1)%7=6→ 位置 6 空 → 放 [6]=26
0: 1:50 2: 3: 4: 5:12 6:26链地址法示例：
0: [18] → [29]
1: [12]
2: [23] → [34]
3: [45]
💡 线性探测：冲突就往后挪一格（di=1,2,3...）；链地址：冲突就挂到链表上。真题考"选哪种方法"居多。
🚨 红牌警告
装填因子 α = 表中记录数 / 哈希表长度 α 越大 → 冲突越多 → 查找效率越低 一般控制 α 在 0.7~0.8 以下
3.6 查找算法对比总结
| 算法 | 存储结构 | 时间复杂度 | 适用场景 |
|---|---|---|---|
| 顺序查找 | 数组/链表 | O(n) | 无序小数据 |
| 折半查找 | 有序数组 | O(log n) | 有序不常变 |
| 分块查找 | 块间有序 | O(√n) | 块间有序 |
| 哈希查找 | 哈希表 | O(1)~O(n) | 关键字快速定位 |
💡 场景判断口诀：无序小数据→顺序；有序不变→折半；频繁增删→顺序/链式（折半不适合链表）；要求最快→哈希（但占空间、有冲突）。
④ 🧪【真题同源例题】
例题 1：入门基础题（先热热身）
对有序表 [5, 13, 19, 21, 37, 56, 64]，用折半查找找 21，需要比较几次？
逐项推演（表格化）：
| 步骤 | low | high | mid | arr[mid] | 比较 | 操作 |
|---|---|---|---|---|---|---|
| 1 | 0 | 6 | 3 | 21 | 21==21 | 找到！ |
运气好，一次就中（21 正好在中间位置 3）。共 1 次。 💡 这就是为什么"中间值"最好找——mid 第一次就可能命中。
例题 2：2024 真题改编（折半次数）
通过折半查找对关键字序列 {12, 18, 21, 35, 45, 55, 66}，查找 21 需要查找（ ）次
A. 4 B. 3 C. 2 D. 1
逐项推演：
| 步骤 | low | high | mid | arr[mid] | 比较 | 操作 |
|---|---|---|---|---|---|---|
| 1 | 0 | 6 | 3 | 35 | 21<35 | high=2（左半） |
| 2 | 0 | 2 | 1 | 18 | 21>18 | low=2（右半） |
| 3 | 2 | 2 | 2 | 21 | 21==21 | 找到 |
✅ 答案：B. 3 次。三步：mid=35 → 18 → 21。陷阱 A（4次）多算一次。
例题 3：2021 真题改编（哈希地址）
表 {5, 14, 23, 32, 41}，H(k)=k%9，散列地址为 5 的元素个数是（ ）
A. 1 B. 2 C. 3 D. 0
逐元素推演：
| k | k%9 | 地址 |
|---|---|---|
| 5 | 5 | 5 |
| 14 | 5 | 5 |
| 23 | 5 | 5 |
| 32 | 5 | 5 |
| 41 | 5 | 5 |
全部映射到地址 5！个数 = 5……等等，5 个元素都 %9 得 5？因为 5,14,23,32,41 公差 9，余数全是 5。 ✅ 答案：地址 5 的元素个数 = 5（全冲突！） 💡 真题 2021 的 {3,12,24,46,10,20} 是余数 3,3,6,1,1,2 地址 0 个数=0。规律：余数相同=冲突。
例题 4：2026 真题改编（复杂度）
对长度为 n 的有序表进行折半查找，平均时间复杂度是（ ）
A. O(1) B. O(log n) C. O(n) D. O(n log n)
逐项分析：
- 每次比较排除一半 → 比较次数 = log₂n 量级
- A O(1)：哈希理想情况，折半不是 ❌
- B O(log n)：排除一半，正确 ✅
- C O(n)：顺序查找 ❌
- D O(n log n)：排序算法 ❌
✅ 答案：B. O(log n)（2026 单选15 原题）
⑤ ⚠️【历年真题高频扣分坑】
| # | 陷阱 | 错误做法 | 正确做法 | 出处 |
|---|---|---|---|---|
| 1 | 链表折半 | 以为有序链表能折半 | 必须顺序存储+有序（随机访问） | 2021 单选13、2023 单选17 |
| 2 | mid 边界错 | 去左半用 low=mid+1 | 去左半 high=mid-1，去右半 low=mid+1 | 2024 单选13 |
| 3 | 次数多数一次 | 折半找 21 算 4 次 | 3 次（mid=35→18→21） | 2024 单选13 |
| 4 | 哈希余数算错 | 12%9 算成 2 | 12%9=3 | 2021 单选12 |
| 5 | 地址 0 个数 | 以为有元素在 0 | 余数无 0 → 个数 0 | 2021 单选12 |
| 6 | 复杂度选 O(n) | 折半当顺序 | 每次排除一半 → O(log n) | 2026 单选15 |
| 7 | ASL 公式混用 | 顺序/折半 ASL 混 | 顺序 (n+1)/2，折半 log₂(n+1)-1 | 经典 |
| 8 | 冲突方法漏项 | 只记线性探测 | 开放定址（线性/平方）+ 链地址 | 经典 |
| 9 | 装填因子理解 | 以为 α 大更好 | α 越大冲突越多效率越低 | 经典 |
| 10 | 无序用折半 | 无序表直接折半 | 必须先排序（有代价） | 经典 |
📌 最值钱的一条：第 1 条（折半必须顺序存储）2021/2023 两年单选原题都考；而第 2、3 条（mid 推演）是 2024 单选13 的核心——"有序+数组"前提和"三步推演"是本章两大得分点。
⑥ 📝【课后自测练习题】
1. 通过折半查找对关键字序列 {3, 12, 24, 35, 46, 55, 66}，查找 46 需要查找（ ）次（2024 真题风格）
A. 4 B. 3 C. 2 D. 1
2. 表 {7, 16, 25, 34, 43}，H(k)=k%9，散列地址为 7 的元素个数是（ ）（2021 真题风格）
A. 5 B. 4 C. 3 D. 0
3. 适用于折半查找的存储结构是（ ）（2021/2023 真题风格）
A. 链式有序 B. 链式无序 C. 顺序无序 D. 顺序有序
4. 对长度为 n 的有序表折半查找，平均时间复杂度是（ ）（2026 真题风格）
A. O(1) B. O(n) C. O(log n) D. O(n log n)
👆 点击展开参考答案与解析
第1题：B. 3 次
- mid=(0+6)/2=3 → arr[3]=35，46>35 → low=4
- mid=(4+6)/2=5 → arr[5]=55，46<55 → high=4
- mid=(4+4)/2=4 → arr[4]=46 ✅ 找到
- 共 3 次
第2题：A. 5
- 7%9=7, 16%9=7, 25%9=7, 34%9=7, 43%9=7 → 全部地址 7，共 5 个（公差 9 全冲突）
第3题：D. 顺序有序
- 折半必须顺序存储（数组）+ 有序（2021 单选13 原题）
第4题：C. O(log n)
- 每次排除一半 → log₂n 量级（2026 单选15 原题）
📝 原有闭卷真题挑战（保留原内容）
（点击下方空白查看答案）
1. 折半查找的适用条件？
2. 顺序查找的平均查找长度 ASL 是？
3. 哈希装填因子 α 的定义？
4. 解决哈希冲突的两种常见方法？
5. 一个有序表 [5,13,19,21,37,56,64,75,80,88,92]
用折半查找找21，比较过程是？👆 点击展开答案
- 顺序存储且有序（链表不能用折半查找）
- ASL = (n+1)/2
- α = 已存元素数 / 哈希表总长度
- 开放定址法（线性探测、平方探测）和链地址法
- mid = (0+10)/2 = 5 → arr[5]=56, 21<56, 去左半 mid = (0+4)/2 = 2 → arr[2]=19, 21>19, 去右半 mid = (3+4)/2 = 3 → arr[3]=21 ✅ 找到！ 共比较 3次
📖 教材习题对照
| 教材习题 | 知识点 | 难度 |
|---|---|---|
| 习题9.1~9.2 | 顺序查找与折半查找 | ⭐⭐ |
| 习题9.3 | 分块查找 | ⭐⭐⭐ |
| 习题9.4~9.5 | 哈希表构造与冲突处理 | ⭐⭐⭐⭐ |
对应教材：严蔚敏《数据结构》C语言版 第2版 → 第9章 查找 对应考试大纲：考点18 — 查找
📺 配套视频
复习到本考点 → 先看视频补讲，再刷上面「闭卷挑战」。