今天这篇聊查找。数据结构学到第十二篇前面的线性表、树、图、字符串、排序基本都过了一遍终于轮到查找。查找这两个字放在前面的知识体系里看其实是个“集大成”的章节——线性表里有顺序查找有序表里有二分查找树里有二叉搜索树和B树还有一套完全不依赖比较的哈希方案。工作中最常见的性能瓶颈十有八九也出在“从一个大数据集里把目标数据捞出来”这个动作上。这篇我会把查找的主流思路完整过一遍包括基础查找的ASL计算方法、树形查找为什么能快、哈希查找为什么是O(1)、字符串查找在文本编辑器里的加速原理以及命令行、编辑器、业务代码中的查找实战。无论你是准备考研、应付期末考试还是在工作中写检索模块这篇都能当一份索引表来用。废话不多说直接进正题。1. 查找的基本盘从线性表里按图索骥查找问题最朴素的形态就是给你一堆数据再给你一个关键字让你找出对应的记录。这一节先讲清楚三个最基础的方案顺序查找、二分查找、分块查找。别看这三兄弟简单很多复杂问题拆到底都是它们的变形。1.1 用ASL给查找算法打分对比查找算法不能光凭感觉说“快”或“慢”得有个量化指标。教科书的答案是平均查找长度Average Search LengthASL。ASL的定义很直白把所有查找情况下的比较次数加起来取平均。公式长这样[ ASL \sum_{i1}^{n} p_i \cdot c_i ]其中 (p_i) 是查找第 i 个元素的概率如果默认每个元素等概率那 (p_i 1/n)(c_i) 是找到第 i 个元素需要比较的次数。你可以把ASL理解成“猜数字游戏的平均次数”。比如从1到100猜一个数每次都从第一个开始顺序猜平均要猜 (1001)/2 50.5 次如果每次都二分最多7次就能锁定。这个数字直接决定了算法在数据量大时的命运。这里有个细节容易被忽略ASL通常分“查找成功”和“查找失败”两种。很多教材和考题只关注成功时的ASL但实际工程里那些查不到数据的场景往往才是性能杀手。比如一个缓存系统大量请求命不中每次都要走一遍完整的查找链路失败ASL才是你真正要优化的指标。1.2 顺序查找最朴素但别小看它顺序查找的思想是零门槛的从头到尾遍历逐个比比中了就返回。适用场景是线性表不管有序无序都能用链表也只能用它因为链表没有随机访问能力。它的成功ASL是 (n1)/2。为什么因为第一个元素比较1次第二个比较2次第n个比较n次总和 n(n1)/2除以n就是 (n1)/2。失败时需要比较n1次才能确认查无此人。代码实现上有个经典优化叫“哨兵”。核心思路是在表头或者表尾放一个目标值循环里就不用每次判断“是否越界”了。我用C写个例子// a[0] 留作哨兵位数据存在 a[1]..a[n] int seq_search(int a[], int n, int key) { int i; a[0] key; // 哨兵 for (i n; a[i] ! key; i--) { ; // 空循环体 } return i; // 返回0表示未找到 }哨兵的实际意义不是降低复杂度而是减少循环里的判断次数。原来每个循环要判断i n和a[i] key两个条件现在只需要判断一个相等条件。数据规模上去后CPU分支预测的压力会小一些实测在大数组遍历场景下能省10%到20%的时间。我当年第一次看到这个写法觉得是雕虫小技后来做检索服务压测时才发现这种细微差别在热路径上真的会被放大。1.3 二分查找区间的艺术二分查找的前提是有序表或者是你愿意先花代价把数据排好序。它的核心思想是“折半收缩”每次拿中间元素跟目标比把查找区间缩一半。很多初学者最难绕明白的是边界条件也就是while循环里到底写left right还是left right以及right mid还是right mid - 1。我的习惯是“盯住区间定义不放松”如果区间是左闭右闭[left, right]那么初始化left 0, right n-1循环条件是left rightmid 不相等时更新为mid - 1或mid 1如果区间是左闭右开[left, right)初始化right n循环条件是left right更新时right midleft mid 1。给一个最经典的左闭右闭实现int binary_search(int a[], int n, int key) { int left 0, right n - 1; while (left right) { int mid left (right - left) / 2; if (a[mid] key) { return mid; } if (a[mid] key) { left mid 1; } else { right mid - 1; } } return -1; }注意mid我写的是left (right - left) / 2不是(left right) / 2。后者在left right溢出时会出问题虽然现在多数语言和平台是64位整型但这是很多大厂面试题明确要考察的点最好从一开始就养成习惯。在C的STL里std::lower_bound和std::upper_bound就是基于二分实现的。刷算法题的时候很多人喜欢手写二分但实际工程里更推荐直接用库函数标准库实现经过了充分测试边界处理比你手搓的可靠得多。PTA这类平台上的“二分查找函数题”考的就是你能不能把边界写对建议把两种区间写法都练熟到时候信手拈来。二分查找的时间复杂度是 O(log n)但它最大的局限是要求数据有序。一旦数据频繁插入删除维护有序性的成本就会吃掉二分查找带来的收益这时候就得想别的办法了。1.4 分块查找折中方案的教科书模板分块查找介于顺序查找和二分查找之间。思路是提前把数据分成若干块块间有序、块内无序。什么意思呢比如第一块里所有元素都比第二块小第二块又都比第三块小但每块内部是乱序的。再利用一个索引表记录每块的最大值和起始位置。查找时先查索引表因为索引表有序可以顺序也可以二分定位到具体哪一块再进块内做顺序查找。它的ASL大约是索引表查找的ASL加上块内顺序查找的ASL。如果分成 b 块、每块 s 个元素用顺序查找索引表时成功ASL约等于 (b1)/2 (s1)/2。当 s ≈ √n 时整体约等于 √n 1。分块查找在实际应用里其实比想象中常见。文件系统的目录索引、数据库的页目录设计背后都有类似“先粗定位、再细扫”的思路。学它的意义不是让你在业务代码里手动实现分块索引而是理解“分级检索”能换来多大的性能提升。哈希的分桶是分级检索B树的多层索引也是分级检索它们都是分块思想在更高维度上的演化。2. 树形查找把比较结果组织成结构线性表做查找问题是“比较结果”没被保留下来。顺序查找这次比较完下次还得从头比二分查找虽然每次砍掉一半但底层还是数组插入删除代价高。树形结构提供了一个新思路把每次比较的结果沉淀到树的分支上让查找路径成为数据结构的一部分。2.1 二叉搜索树理解查找和插入是一回事二叉搜索树的定义不长对于任意节点左子树所有节点值都小于它右子树所有节点值都大于它。查找就是一场从根节点出发的“猜大小”游戏比节点大往右走比节点小往左走走到空节点说明查无此值。插入和查找是同构的都是先走一遍查找路径走到空位时把新节点放进去。但删除要复杂一些分三种情况叶子节点直接删掉父节点对应指针置空。只有一个孩子让这个孩子顶替被删节点的位置。有两个孩子用中序前驱或中序后继也就是左子树最大节点或右子树最小节点来替换被删节点的值然后删掉那个替身节点。第三种情况很容易写漏。我见过很多初学者的代码删除双子节点后没有递归处理替身节点的删除结果树上留下一个重复值。简单写个C的结构示意struct Node { int val; Node *left, *right; Node(int v) : val(v), left(nullptr), right(nullptr) {} }; Node* deleteNode(Node* root, int key) { if (!root) return nullptr; if (key root-val) { root-left deleteNode(root-left, key); } else if (key root-val) { root-right deleteNode(root-right, key); } else { // 情况1叶子节点 if (!root-left !root-right) { delete root; return nullptr; } // 情况2只有一个孩子 if (!root-left) { Node* rightChild root-right; delete root; return rightChild; } if (!root-right) { Node* leftChild root-left; delete root; return leftChild; } // 情况3有两个孩子找右子树最小节点替换 Node* minNode root-right; while (minNode-left) minNode minNode-left; root-val minNode-val; root-right deleteNode(root-right, minNode-val); } return root; }二叉搜索树的平均查找长度为 O(log n)但前提是树长得“匀称”。如果你按升序往空树里插入 1, 2, 3, 4, 5树会退化成一条链查找复杂度直接退化成 O(n)。这就是为什么平衡树出现了。2.2 平衡树别让二叉树退化成链表解决退化问题的思路是“在插入删除后自我调整”。教科书里讲的AVL树是最严格的平衡树它要求任意节点的左右子树高度差不超过1。插入节点后如果发现某节点失衡通过四种旋转来恢复LL型右旋、RR型左旋、LR型先左旋再右旋、RL型先右旋再左旋。AVL的查找性能非常稳定严格O(log n)但它的代价是插入删除时为了维持绝对平衡可能频繁触发旋转写起来也复杂。工程里更常见的其实是红黑树。红黑树放宽了平衡条件不要求左右子树高度严格相等只要求最长路径不超过最短路径的两倍。它用颜色标记节点通过变色和旋转维持五个性质节点非黑即红、根是黑、红节点的孩子是黑、叶子节点是黑、从任意节点到每个叶子的路径上黑节点数相同。C的std::map、Java 的TreeMap底层都是红黑树。为什么工程选红黑树而不是AVL因为插入删除更友好。AVL对平衡太敏感每次插入很可能要一直旋转到根红黑树最多三次旋转就能搞定虽然它的查找常数比AVL略大但综合读写场景红黑树的整体效率更优。如果你是做缓存服务这类“查多写少”的场景AVL反而可能更合适如果是通用有序容器红黑树是更稳的默认选择。2.3 B树磁盘索引为什么选它如果说AVL和红黑树是为“内存场景”设计的那么B/B树就是为“磁盘场景”量身定制的。为什么因为在磁盘上读写一个数据块的开销远大于内存比较IO次数才是主要矛盾。B树的特点是多路平衡搜索树每个节点可以存多个关键字非叶子节点只存索引不存实际数据所有数据都挂在叶子节点上叶子节点之间用指针串成链表。这意味着树高更低查一个叶子节点需要的IO次数更少。假设每个节点可以存几百个键三层的B树就能支撑千万级数据量这对数据库索引来说非常划算。MySQL的InnoDB索引用的就是B树。三个关键设计值得细品非叶子节点不存数据一页就能装下更多键树会更矮。叶子节点包含所有数据且有序排列天然支持范围查询比如SELECT ... WHERE id BETWEEN 100 AND 200找到100后顺着叶子链表往后扫就行。节点大小按磁盘页大小设计读取一个节点正好一次IO。我见过一些同学用二叉平衡树来设计磁盘索引思路没错但忽略了磁盘读取的单位是“页”而不是“个节点”。一棵百万节点的二叉树树高20多最坏要20多次磁盘IO换成四阶以上的B树树高可能只要3到4层。这就是数据结构设计跟实际存储介质紧密结合的意义。这部分内容考研和面试都是高权重考点值得反复琢磨。3. 哈希查找把查找变成一次计算前面的查找算法本质都是“比较”无非是比较的方式和载体不同。哈希查找换了一条路不比较直接算。3.1 哈希函数储柜号码牌的游戏你去游泳馆存东西前台给你一个手环上面写着柜号。下次来取物品靠手环直接走到对应柜子不用一个柜一个柜去开。哈希查找就是这个逻辑设计一个函数 f把关键字映射成存储地址查找时用同一个函数算一下地址直接过去取。最常用的哈希函数是除留余数法hash(key) key % p。这里的 p 选择很有讲究。如果 p 取10而你存储的key恰好都是10的倍数那么所有key都会被映射到下标0的位置哈希表退化成链表性能直接崩塌。所以 p 通常选“接近表长度的质数”让余数分布更均匀。另一个思路是数字分析法分析关键字集合的分布挑出分布足够分散的几位作为哈希地址。还有平方取中法把关键字平方后取中间几位。这些方法没有绝对优劣核心诉求只有一个——让哈希地址尽量均匀分布减少冲突。我举个工程里的例子。去重软件要对比大量文件的重复内容通常会先算每个文件的哈希值再查这个哈希值是否已经存在。此时哈希函数的质量直接决定去重效率如果哈希分布不均某个桶积累几十万个文件去重性能就毁了。3.2 哈希冲突的三种处理姿势哈希函数把无限的关键字空间映射到有限的地址空间冲突是不可避免的。处理冲突无非两条路线换个位置或者挂个链子。开放定址法属于“换个位置”。线性探测的思路是如果计算出的位置被人占了就往后一个位置找再占就再往后直到找到空位。它的缺点是容易产生“堆积”一旦某个区域聚集了大量元素后续插入和查找都要走很远。二次探测会好一些按 1², -1², 2², -2² 的步长跳跃可以缓解堆积但仍有踩坑风险。链地址法属于“挂个链子”。每个桶不再是单个元素而是一个链表或更复杂的数据结构:class HashTable: def __init__(self, size16): self.size size self.table [[] for _ in range(size)] def _hash(self, key: int) - int: return key % self.size def put(self, key: int, value): h self._hash(key) for i, (k, v) in enumerate(self.table[h]): if k key: self.table[h][i] (key, value) return self.table[h].append((key, value)) def get(self, key: int): h self._hash(key) for k, v in self.table[h]: if k key: return v return None链地址法实现简单删除也方便不用担心被占用位置堵住后面的查找路径。Java 8 的 HashMap 在链表长度超过8且容量达到64时会把链表转成红黑树本质上就是在链地址法基础上做了个“升级”防止极端情况下冲突链太长导致性能劣化。还有一个关键指标叫负载因子load factor等于存储元素个数除以表长度。负载因子越高冲突概率越大。Java HashMap 默认在 0.75 时扩容扩容后要重新散列所有元素也就是 rehash。Python 的 dict 扩容策略类似也是动态调整表大小来维持较低的负载因子。3.3 工程里的哈希HashMap、缓存与去重哈希查找在工程里太常见了。HashMap/HashSet 的平均查找复杂度是 O(1)是内存里做等值查找的默认选择。缓存系统里的 key-value 存储绝大多数底层都是一个巨大的哈希表。但哈希表也不是银弹。它的两大短板是不支持范围查询和不支持按顺序遍历。你想查“所有价格在100到200之间的商品”哈希表无能为力你只能遍历全部元素一个个比对但B树对这个查询非常友好因为叶子节点本身是有序链表。这也就是为什么数据库里既有B树索引也支持哈希索引两类索引服务不同的查询场景。哈希还有个有趣的工程应用是一致性哈希。缓存服务器扩容缩容时如果简单用hash(key) % N来路由节点数量一变几乎所有key都会落到新位置缓存就全失效了。一致性哈希把哈希值空间组织成一个环形结构让每个key只影响附近一小段节点扩容缩容只影响局部数据这是分布式缓存里非常经典的查找设计。去重场景也离不开哈希。重复文件查找软件的原理就是先对文件内容算哈希值用哈希快速圈定“可能相同的文件组”再对这些组做逐字节比对。哈希让“判断两个文件是否相同”这个潜在O(n)问题变成O(1)的等值判断省掉了海量字节比较。4. 字符串查找与实战场景中的查找前面讨论的查找对象大多是数值或结构化记录。实际开发里另一个高频场景是字符串查找它和普通查找的思维方式很不一样值得单独拎出来讲。后面我再带你看一些日常工作里最常见的查找场景命令行找文件、编辑器里正则替换、Excel取数据、二进制数据查找这些本质上都逃不出前面几节讲的那几类算法。4.1 KMP、BM、Sunday字符串查找的加速矩阵先想一个最简单的问题在一个长文本里找一个模式串比如在整本小说里找“数据结构”四个字。最朴素的做法是把模式串对齐到文本的每一个位置逐个字符比对发现不一致就整体后移一位。匹配成功是O(n)匹配失败时最坏是O(n*m)这也是为什么大文档里用暴力匹配做搜索会卡顿。KMP算法的核心是“匹配失败时不回退文本指针”。它提前计算出模式串每个位置的最长公共前后缀形成一个next数组。当某个字符匹配失败时借助next数组直接让模式串跳到合适的位置而不是只移动一位。这里给一份Python的KMP实现方便你直接跑通细节def get_next(p: str): n len(p) nxt [-1] * n j, k 0, -1 while j n - 1: if k -1 or p[j] p[k]: j 1 k 1 nxt[j] k else: k nxt[k] return nxt def kmp_search(text: str, pattern: str): nxt get_next(pattern) i j 0 while i len(text) and j len(pattern): if j -1 or text[i] pattern[j]: i 1 j 1 else: j nxt[j] if j len(pattern): return i - j return -1拿模式串ABABAC来说next 数组算出来是[-1, 0, 0, 1, 2, 0]。它的含义是如果某个位置失配模式串可以安全跳过的距离。你可以手算一遍能加深理解。KMP的时间复杂度稳定在O(nm)非常适合需要反复搜索同一模式串的场景比如文本编辑器的“查找全部”。BM算法走的是另一条路线从模式串尾部开始匹配利用“坏字符规则”和“好后缀规则”决定移动距离。很多实际搜索场景里BM的速度比KMP更快因为它在不相匹配时能一次跳过更多字符。Sunday算法思路更简单匹配失败时检查文本串中模式串后一位的那个字符用它最后一次在模式串中出现的位置来决定位移。文本编辑器的搜索功能、IDE的全局检索底层基本都是这些算法的工程化变体。你不用每次自己实现它们但遇到线上搜索性能问题时知道该往哪个方向查会很有帮助。4.2 命令行与编辑器里的查找技巧字符串查找不只是算法题里的概念日常工作中你天天都在用只是很多操作没意识到背后的原理。Linux 下最常被低估的查找命令是find。它能按文件名、类型、大小、时间条件组合过滤。比如找目录下大于10M的文件find /data -type f -size 10M这条命令的意思是在 /data 目录下找类型为普通文件、大小超过10MB的文件。10M表示大于10MB-10M表示小于10MB不加符号就是正好10MB。常见的组合还有-name *.log按名字过滤-mtime -7找7天内修改过的文件。find文件的逻辑本质上就是一次“树形结构遍历条件匹配”从目录节点开始递归地走每个文件都算一个叶子节点匹配条件就输出。如果你对Linux目录树的结构熟悉就能预期 find 的耗时和遍历范围。编辑器里的正则查找替换也是个高频操作。VSCode、JetBrains 系列都支持正则模式比如把日志里的时间戳格式统一^ERROR.*timeout用正则就能把所有包含 ERROR 和 timeout 的行筛出来。替换时还可以用捕获组比如^(\d{4})-(\d{2})-(\d{2})匹配日期替换成$3/$2/$1就能改成需要的格式。正则表达式本质上是定义了一个有限状态机匹配过程就是在文本上驱动状态迁移这和KMP是同一层级的自动化思想只是表达能力更强、代价也更大。4.3 业务代码里的查找从Excel到数据库到二进制实际写业务代码时查找跟各种数据载体绑定在一起不像算法题里给个数组那么简单。一个很常见的需求是“在Excel里找包含某个关键字的行”。用 Python 的 openpyxl 可以很快搞定from openpyxl import load_workbook wb load_workbook(订单.xlsx) ws wb.active for row in ws.iter_rows(values_onlyTrue): for cell in row: if cell and 待查找关键字 in str(cell): print(row) break这个写法本质上是顺序查找把每一行每个单元格都遍历一遍。如果Excel很大或者你要经常查更高效的做法是先建一个内存索引比如字典把关键字映射到行号后续查询就是O(1)。数据库里查一条记录比如桌面应用程序点击“查询”按钮通常执行一条带 WHERE 条件的SQL。InnoDB会优先走主键或索引查找这就是我们前面讲的B树查找而不是全表扫描。写SQL时如果查询条件里的列没有索引数据库只能做全表顺序扫描数据量大时慢得离谱。很多时候你给某列加个索引查询性能立刻翻倍只不过索引的构建和B树的结构条文都看不见摸不着才显得“玄学”。还有一种容易出事的场景是二进制数据查找。C语言里查字符串常用strstr但它依赖字符串以\0结束如果你要在一个二进制缓冲区里找一段模式串strstr会在遇到\0时提前停止结果是错的。GNU的memmem扩展可以指定长度可以用于二进制内存查找但其内部通常是基于双指针的暴力匹配。如果二进制数据很大且需要多次查找就该考虑实现KMP或Sunday算法来加速了。很多协议解析、病毒特征匹配、固件分析工具底层都在处理这类问题。5. 选型、避坑与我的实操体会前四节把查找算法的原理和应用讲得差不多了最后做一个横向的“选型速查”和“翻车点汇总”。这一节更像是我自己的工具手册你写代码遇到查找场景时直接拿来对号入座。5.1 复杂度速查表与选型建议查找算法平均时间复杂度最坏时间复杂度空间复杂度适用场景顺序查找O(n)O(n)O(1)小规模、无序、链表二分查找O(log n)O(log n)O(1)有序静态数组分块查找O(√n)O(n)O(√n)块间有序、动态变化不大的数据二叉搜索树O(log n)O(n)O(n)动态插入删除但要注意退化AVL/红黑树O(log n)O(log n)O(n)动态有序数据范围查询B树O(log_m n)O(log_m n)O(n)数据库和文件系统索引哈希查找O(1)O(n)O(n)等值查询、去重、缓存KMP字符串匹配O(nm)O(nm)O(m)长文本中反复匹配同一模式串选型经验我个人总结成一句话“要等值查询用哈希要范围查询用树要磁盘IO友好就上B树数据量小且无序那就顺序查找最省事。”我见过不少人在只需要几百条数据的配置表上硬上一套HashMap或者红黑树结果代码复杂度变高性能提升却可以忽略不计。小数据场景下顺序查找因为缓存局部性好经常是最快的。数据结构选型要匹配数据规模这是“了解算法复杂度”和“真正会选算法”的分水岭。5.2 七个高频翻车点与排查方案第一二分查找死循环或漏查。最常见的原因是边界写错。左闭右闭和左闭右开混着写可能导致漏掉某个元素或者死循环。排查办法就是咬死一种区间定义并做几个小用例验证单元素数组、双元素数组、目标不存在且小于最小、目标不存在且大于最大。第二二叉搜索树插入有序数据后性能崩塌。很多人测试时用随机数据没发现退化真到了生产环境数据是递增ID树退化成链表查找从O(log n)变成O(n)。最直接的规避方案是使用平衡树实现C的map、Java的TreeMap不要手写裸BST去做长期运行的服务。第三哈希表负载因子失控导致严重退化。如果自定义哈希表却没实现扩容数据一多冲突链越来越长查找退化到O(n)。在Java里直接配好初始容量和负载因子在Python里则要避免把大量对象塞进一个dict后频繁修改导致rehash风暴。第四KMP的next数组算错。建议手算一遍小例子比如模式串ABABAC然后用代码输出next数组跟你手算的对一下。如果失配时回退位置不对问题多半出在next数组的构建逻辑上。第五在超大文本里用朴素匹配。一次性在几MB的文本里搜索朴素匹配往往也能跑完但如果在几百MB的日志文件里反复查暴力匹配会痛苦到崩溃。此时应改用KMP、BM或者正则引擎并考虑先按行拆分、或建索引等方案。第六用strstr在二进制数据里找模式串。前面已经说过二进制数据可能包含\0下意识地使用strstr会得到错误结果。记住二进制查找要用指定长度的匹配方式要么memmemGNU扩展要么自己实现KMP/Sunday算法。第七find命令条件组合不当导致全盘扫描。在根目录直接跑find / -name xxx可能耗时极长。合理做法是缩小搜索范围或者先过滤掉某些目录。常用技巧是加-path ./proc -prune -o这类参数跳过系统目录。5.3 我自己的一点体会真到自己写代码我越来越觉得这些查找算法考的不是背模板而是训练你对数据组织方式的敏感度。二分查找考验的是你对区间不变式的理解哈希考验的是你对地址空间的规划B树考验的是你对存储介质的理解。遇到查找性能问题先问自己四个问题数据在内存还是磁盘数据动不动等值查询多还是范围查询多查询频率高不高这四个问题回答完用哪类算法基本就清晰了。另外查找跟排序永远是兄弟。很多查找方案的前提是数据有序而排序算法的选择又会直接影响初始化成本。如果你只需要一次性查找排个序再二分未必比顺序查找快因为排序本身的代价就摆在那里。我实际项目里最常用的组合是“哈希范围索引”混合使用等值查询走哈希范围排序走索引各司其职这也是不少存储引擎的通用思路。数据结构的价值往往不在某个单独算法的复杂度数字里而在于你能不能在一个真实系统里把不同方案的边界看明白然后把它们拼成一条稳、快、省的通路。