Appearance
查找基本概念
为什么需要查找基本概念
查找是数据结构中最基本的操作之一。无论是数据库检索、搜索引擎还是操作系统的文件管理，底层都离不开查找算法。
408 考研中，查找章节的基本概念是后续学习顺序查找、折半查找、B 树、散列表等具体算法的前提。理解查找表、关键字、ASL 等核心术语，才能正确分析各种查找算法的效率。
核心思想
查找表
查找表（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（失败） | 时间复杂度 | 适用结构 |
|---|---|---|---|---|
| 顺序查找 | (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 分析中的应用（结合折半查找考查）