查找基础：顺序查找、折半查找与分块查找

学完树和图之后，再回头看“查找”这个主题，会发现它其实一直贯穿在整个数据结构学习里。顺序表在查找，BST 在查找，哈希表在查找，B+ 树本质上也在查找。只不过不同结构对查找做了不同层次的优化。而在正式进入哈希表和更高级字符串查找之前，先把最基础的几种查找方式梳理清楚，非常有必要。

这一篇主要讨论三种经典基础查找：

  • 顺序查找；
  • 折半查找；
  • 分块查找。

它们很像一条逐步优化的路线：

  • 从最朴素的一个个看；
  • 到利用有序性快速缩小范围；
  • 再到在顺序与索引之间做折中。

所以这一篇最重要的，不是记住三个定义，而是看清：查找效率的提升，往往来自对数据结构和先验条件的更多利用。

一、什么是查找问题

查找问题通常可以概括为：

在一组数据中，判断目标元素是否存在；如果存在，找到它的位置或相关记录。

从最基础的角度看，查找至少会受到两类因素影响：

  • 数据本身是无序还是有序；
  • 是否允许额外建立索引结构。

也正因为如此，不同查找算法适合的前提完全不同。

二、什么是顺序查找

顺序查找，也叫线性查找，是最朴素的一种方式：

  • 从第一个元素开始；
  • 依次和目标值比较；
  • 找到就返回；
  • 找到末尾还没命中则失败。

它最大的特点就是：

  • 几乎不依赖数据的任何额外性质；
  • 无论数据是否有序，都能直接用。

所以顺序查找的意义不在于它多快，而在于它是“零前提、最通用”的起点。

三、顺序查找的复杂度怎么理解

顺序查找的时间复杂度通常是 O(n)。

  • 最好情况：目标在第一个位置；
  • 最坏情况：目标在最后一个位置，或根本不存在；
  • 平均情况：通常也和线性规模同级。

它的缺点显而易见：

  • 数据一大就慢；
  • 每次几乎都可能要扫很多元素。

但它的优点也很直接：

  • 实现简单；
  • 对数据结构要求低；
  • 对动态变化数据也很容易处理。

四、什么是折半查找

折半查找，也叫二分查找，是查找领域里最经典的一种优化。

它的核心思想是：

利用数据有序这一前提，每次比较都把搜索区间缩小一半。

基本过程通常是：

  1. 取当前区间中间元素；
  2. 如果目标值等于它，查找成功；
  3. 如果目标值更小，就去左半区；
  4. 如果目标值更大，就去右半区；
  5. 重复直到找到或区间为空。

五、为什么折半查找必须要求有序

因为它的每一步都在根据中点大小关系“排除一半数据”。

如果数据无序，那么你看到中间元素比目标大，并不能说明目标一定不在右边。也就是说：

  • 没有有序性；
  • 就没有“安全排除”的依据；
  • 折半逻辑就无法成立。

所以二分查找的最大前提一定要牢牢记住：

数据必须是有序且支持随机访问的。

六、为什么折半查找通常是 O(log n)

因为每一次比较都会把问题规模缩小一半。

例如：

  • 第一次从 n 缩到 n/2；
  • 再缩到 n/4；
  • 再缩到 n/8；
  • 直到区间长度变成 1。

这种不断折半的过程，对应的复杂度就是 O(log n)。

这和顺序查找的 O(n) 相比，在大规模数据下差距会非常明显。

七、二分查找有哪些常见变体

很多人一开始只会“找某个值是否存在”的标准写法，但二分查找真正常见的场景其实包括很多变体，例如：

  • 找第一个等于目标值的位置；
  • 找最后一个等于目标值的位置；
  • 找第一个大于等于目标值的位置；
  • 找最后一个小于等于目标值的位置。

这些问题本质上仍然是在有序区间里不断缩小边界，只是终止条件和边界更新细节更考验实现功底。

八、什么是分块查找

分块查找可以理解成一种折中方案：

先把数据分成若干块，对块建立索引；查找时先确定目标可能在哪一块，再在块内做顺序查找。

它的核心思想是：

  • 不像二分查找那样要求整个数据序列全局严格有序；
  • 也不像顺序查找那样完全没有索引；
  • 而是在“额外索引”和“块内扫描”之间取得平衡。

九、分块查找通常怎么做

典型做法通常是：

  1. 把查找表分成若干块；
  2. 每块内部可以无序或弱有序；
  3. 对每块建立一个索引项，例如记录该块最大关键字；
  4. 查找时先在索引表中定位目标属于哪一块；
  5. 再进入对应块内顺序查找。

这样做的好处是：

  • 比纯顺序查找快；
  • 对数据整体有序要求又没那么严格；
  • 索引结构也相对简单。

十、分块查找为什么是一种折中思想

它非常典型地体现了数据结构里的权衡：

  • 纯顺序查找：不建索引，简单但慢；
  • 折半查找：依赖全局有序，快但前提强；
  • 分块查找：加一点索引，换来一部分效率提升。

所以分块查找的价值，不一定在于它今天是否是最高频工业实现，而在于它帮助你理解：

查找效率的改进，往往不是“非黑即白”，而是可以通过局部索引逐步增强。

十一、这三种查找方式怎么比较

1. 顺序查找
  • 最通用；
  • 对数据要求最低；
  • 时间复杂度通常是 O(n)。
2. 折半查找
  • 利用全局有序；
  • 每次缩小一半范围；
  • 时间复杂度通常是 O(log n)；
  • 但必须支持随机访问。
3. 分块查找
  • 介于两者之间；
  • 需要额外建立块索引；
  • 适合索引代价可接受但全局排序不完全理想的场景。

十二、查找算法和底层结构有什么关系

这点非常重要。

  • 顺序查找几乎什么结构都能做；
  • 折半查找通常要求顺序存储或至少高效随机访问；
  • 分块查找则往往依赖某种分段组织与索引维护。

也就是说，查找算法从来不是孤立存在的，它总是和数据如何存储直接绑定。

十三、学习基础查找时最容易踩的坑

1. 无序数据上直接二分

这是原则性错误。

2. 以为二分查找永远最好

如果数据频繁变动、维护有序成本很高，未必划算。

3. 只会最基础二分，不会边界变体

这会导致很多真实问题不会套用。

4. 忽略查找和存储结构之间的关系

很多时候不是算法不够好，而是底层结构本来就不支持。

总结

基础查找方法之所以重要，不只是因为它们简单，而是因为它们构成了后面所有高级查找结构的思维起点。真正值得先建立起来的，是这些核心认识：

  • 顺序查找是零前提、最通用的基础查找方式；
  • 折半查找利用有序性把复杂度降到 O(log n)，但前提强；
  • 分块查找体现了在局部索引和块内扫描之间做折中的思路；
  • 查找效率的提升，本质上来自对数据组织方式的更充分利用；
  • 不同查找方式没有绝对优劣，关键在于数据条件和维护成本；
  • 真正学会查找，不是背几个定义，而是先判断数据是否有序、是否支持随机访问、是否值得建索引。

把这一篇理解透之后，后面再去学哈希表、字符串匹配和跳表时，你会更容易意识到：那些更高级的结构，本质上都是在围绕“如何更快查到东西”继续做更强的结构化优化。

参考资源：