Appearance
查找基本概念
核心思想
查找表
查找表（Search Table）是由同一类型的数据元素组成的集合。根据操作方式不同，分为两类：
| 类型 | 定义 | 操作 | 典型结构 |
|---|---|---|---|
| 静态查找表 | 仅做查找操作的查找表 | 查询某元素是否存在、检索属性 | 顺序表、有序表 |
| 动态查找表 | 查找的同时进行插入/删除 | 查找时插入不存在的元素，或删除已存在的元素 | 二叉排序树、散列表、B 树 |
关键字
关键字（Key）是数据元素中某个数据项的值，用来标识一个数据元素。
- 主关键字：能唯一标识一个数据元素的关键字（如学号）
- 次关键字：能识别若干个数据元素的关键字（如姓名，可能重复）
查找方法分类
根据查找策略的不同，查找方法可分为：
| 分类 | 方法 | 特点 |
|---|---|---|
| 基于比较 | 顺序查找、折半查找、分块查找 | 通过关键字比较来逐步缩小范围 |
| 基于树表 | 二叉排序树、平衡二叉树、B 树/B⁺ 树 | 利用树结构组织数据，适合动态查找 |
| 基于散列 | 散列表（哈希表） | 通过散列函数直接计算地址，不需要比较 |
交互可视化
通过下方的交互动画，你可以逐步观察查找基本概念的执行过程：
操作详解
ASL 的定义
ASL（Average Search Length，平均查找长度）是衡量查找算法效率的关键指标，定义为查找过程中关键字比较次数的期望值。
计算公式：
ASL = Σ(i=1 to n) Pᵢ × Cᵢ其中：
n：查找表中元素个数Pᵢ：查找第 i 个元素的概率（等概率时 Pᵢ = 1/n）Cᵢ：找到第 i 个元素需要的比较次数
查找成功分析
查找成功的 ASL：目标元素在查找表中，找到它所需的平均比较次数。
以顺序查找为例（等概率），查找表有 n 个元素：
- 查找第 1 个元素：比较 1 次
- 查找第 2 个元素：比较 2 次
- ...
- 查找第 n 个元素：比较 n 次
ASL_成功 = (1 + 2 + ... + n) / n = (n + 1) / 2不同查找算法的查找成功 ASL 差异很大，这正是选择查找算法的核心依据。
查找失败分析
查找失败的 ASL：目标元素不在查找表中，确认查找失败所需的平均比较次数。
以顺序查找为例（不带哨兵）：
- 无论目标值是什么，都需要比较 n 次才能确认失败
ASL_失败 = n以折半查找为例，查找失败的比较次数取决于判定树中外部结点（失败结点）的层数，需要根据具体判定树计算每个失败位置的比较次数再求平均值。
注意：408 真题中经常要求分别计算查找成功和查找失败的 ASL，必须区分清楚。
易错：ASL（平均查找长度）是衡量查找效率的核心指标，分为查找成功 ASL 和查找失败 ASL。两者的计算方法不同，分母也不同——成功 ASL 的分母永远是元素个数 n，失败 ASL 的分母不是 n，而是"失败可能落入的位置数"。408 大题高频考查 ASL 计算，混淆分母是第一大丢分点。
失败 ASL 分母速查（做题前先对号）：
| 查找方法 | 失败 ASL 的分母 | 出处 |
|---|---|---|
| 顺序查找（有序表） | n + 1（失败区间数） | 顺序查找 |
| 折半查找 | n + 1（判定树外部结点数） | 折半查找 |
| 散列查找 | 散列函数的值域大小（除留余数法即模数 p——不是表长 m，更不是元素数 n） | 开放定址法 |
复杂度分析
| 查找方法 | ASL（成功） | ASL（失败） | 时间复杂度 | 适用结构 |
|---|---|---|---|---|
| 顺序查找 | (n+1)/2 | n（或 n+1） | O(n) | 无序/有序表 |
| 折半查找 | ≈ log₂(n+1) - 1 | ≈ log₂(n+1) | O(log₂n) | 有序顺序表 |
| 分块查找 | 介于顺序与折半之间 | — | O(√n)（最优） | 分块有序表 |
| 散列查找 | 取决于装填因子 | 取决于装填因子 | 接近 O(1) | 散列表 |
注意：折半查找只适用于有序的顺序存储结构，链表不支持折半查找。
考研高频考点
- ASL 的定义与计算公式（选择题/填空题高频考查）
- 查找成功 ASL 与查找失败 ASL 的区别与计算（大题高频）
- 静态查找表与动态查找表的区分（概念题）
- 各类查找方法的适用条件与 ASL 对比（选择题高频）
- 关键字、主关键字与次关键字的定义（概念题）
- 判定树在 ASL 分析中的应用（结合折半查找考查）
相关知识
- 顺序查找、折半查找、哈希表（开放定址法）分别是三类查找策略（线性扫描、分治、直接定址）的代表
- 二叉排序树（BST）是最基本的动态查找结构，理解其 ASL 分析方法有助于对比静态查找
- 分块查找是顺序查找与折半查找的折中方案，ASL 介于两者之间
- 查找失败 ASL 的"失败区间"概念在折半查找的判定树分析中有完整展开