查找

查找（Searching）是数据结构中的核心操作之一：判断某个给定值是否存在于数据集合中，如果存在，又位于何处。数据库查询、编译器里的符号解析、在缓存中找回一个条目，归根结底都是同一个问题，而答案的代价决定了程序是瞬间返回还是慢吞吞。

在数据规模越来越大、查找越来越频繁的现实场景里，如何用尽可能少的比较次数找到目标元素，就成了绕不开的问题，本章也正是围绕”查找效率”这一核心问题展开。内容从最朴素的策略出发——把待查元素与集合中的每个元素依次比较——再转向那些能跳过大部分无效工作的结构：有序表让查找范围不断折半，哈希表一步跳到目标桶，B 树把庞大的索引压得很浅，每一步只触碰一个磁盘页。其中顺序查找、折半查找和分块查找构成基础的一层，先掌握这三种基本策略；哈希表、B 树与 B+ 树以及字符串匹配则属于进阶的一层，需要理解更复杂的结构与算法。

读完本节，你能够说明顺序查找、折半查找与分块查找各自的基本思想及其复杂度，也能解释 B 树与 B+ 树的结构形态以及一次查找在其中的行进路径。你会动手构造哈希表并分析冲突处理方式与装填因子对性能的影响，实现朴素匹配与 KMP 字符串匹配，并学会根据数据本身的特点挑选合适的查找算法。