title: 查找 tags:

module
data-structure-and-algorithm
search
joplin type: module source_type: reconstructed created: 2026-04-22 updated: 2026-04-22 ---

查找

[!abstract] 这一模块处理“如何快速找到目标元素”这个核心问题。复习时重点不是背函数名，而是理解不同查找方式对数据有序性和结构的依赖。

模块结论

[[查找算法]] 的核心是利用已有结构信息减少比较次数。
顺序查找适用范围最广，但效率通常较低。
折半查找要求有序顺序表，这是它高效的前提，不是白来的。

一、顺序查找

从头到尾逐个比较。
优点是实现简单，对存储结构要求低。
缺点是平均比较次数较多。

二、折半查找

要求表有序且支持随机访问。
每次比较后把查找区间缩小一半。
典型复杂度是 O(log n)。

为什么链表不适合折半查找

因为折半查找依赖快速定位中间位置。
链表访问中间结点代价高，无法发挥折半优势。

三、查找结构与查找代价

静态查找更关注查找效率。
动态查找还要考虑插入删除成本。
所以不同结构会引出顺序表、二叉排序树、平衡树、哈希等不同方案。

四、查找判定思维

先看数据是否有序。
再看是否允许随机访问。
最后看结构是静态还是动态变化。

五、易错点

折半查找快，不代表它适用所有场景。
有序只是条件之一，还要有合适的存储结构。
动态查找时不能只看一次查询速度，还要看维护代价。

六、复习提问

折半查找为什么要求有序顺序表？
查找问题为什么会引出树结构而不止是数组？
静态查找和动态查找各自更关注什么？

来源

[[raw/Joplin/计算机专业基础/数据结构与算法/(C)840数据结构与算法/4.查找.md]]
[[raw/Joplin/计算机专业基础/数据结构与算法/(C)840数据结构与算法/5.二叉排序树.md]]
[[raw/Joplin/计算机专业基础/数据结构与算法/(C++)数据结构与算法/12.二叉排序树.md]]

相关页面

[[数据结构与算法]]
[[查找算法]]
[[二叉排序树]]
[[AVL树]]