★ FEATURED ARTICLE 1. 为什么“查找”这一章值得单独拎出来总结如果你正在学《数据结构》翻到第七章“查找”的时候大概率会有一种感觉前面线性表、树、图已经够折腾了怎么又冒出来一章看起来像“复习”的内容我当初也是这么想的直到后来做项目、准备面试、帮别人改代码才发现查找这一章其实是整个数据结构里最“接地气”的一章——它不跟你讲虚的直接告诉你在一堆数据里怎么最快找到你想要的那个。这一章的核心关键词就三个查找表、平均查找长度ASL、动态与静态。你把这三点吃透后面不管是手写二叉排序树、做哈希冲突处理还是分析为什么数据库索引要用B树都能找到根。我写这篇总结的出发点很简单教材上的定义太干考试要考、面试要问、实际写代码要用但很多人学完只记得“折半查找很快”问他快在哪、什么条件下快、快多少就说不清了。所以这篇内容适合三类人正在学这门课、需要一份能直接背也能直接理解的总结的人准备技术面试、想把查找这块讲清楚的人以及写过一些代码但没系统梳理过查找结构、想补一补底层逻辑的人。我会按“整体设计思路→核心结构逐个拆→实操分析→常见坑”的顺序来尽量把每个结论背后的“为什么”讲透而不是只丢公式。2. 查找这一章的整体设计思路拆解2.1 先分清静态查找和动态查找到底差在哪教材一上来就分静态查找表和动态查找表很多人背了定义就过了。但这两个词的区别直接决定了你该选什么结构。静态查找表的意思是数据集合建好之后主要操作就是“查”很少甚至不插入、不删除。比如一个字典文件、一张固定的配置表。动态查找表则相反查的过程中还会频繁插入和删除比如一个实时更新的用户在线列表。为什么这个区分重要因为静态场景下你可以用顺序表加折半查找简单又快但动态场景下如果你还用有序数组每次插入都要挪一堆元素代价是O(n)。这时候就该上二叉排序树、平衡树或者哈希表。我见过不少人一上来就说“折半查找最好”结果在一个频繁插入的场景里用有序数组插入一次挪半天这就是没分清动静的后果。提示判断用哪种查找结构先问自己一句话——这个数据集是“建好就不怎么动”还是“边查边改”答案不同选型完全不同。2.2 平均查找长度ASL衡量查找效率的统一尺子ASL全称Average Search Length中文叫平均查找长度。它的定义是查找过程中关键字的比较次数的期望值。公式写出来是ASL Σ(Pi × Ci)其中Pi是查第i个元素的概率Ci是找到它需要的比较次数。考试里通常假设每个元素查找概率相等也就是Pi 1/n那ASL就变成比较次数的平均值。这个指标为什么是这一章的“灵魂”因为不同的查找方法本质上就是在比谁的ASL更小。顺序查找ASL是(n1)/2折半查找大约是log₂(n1)-1哈希查找理想情况下接近1。你把这几个数放一起就能直观感受到差距n1000的时候顺序查找平均要比较500次折半查找大约9次哈希理想情况1次。这就是为什么我们要折腾那么多结构。我个人的经验是ASL不只是一个考试公式它其实是你评估任何查找方案的通用思维模型。哪怕你用的是数据库索引、缓存背后衡量好坏的核心逻辑依然是“平均要比较/访问多少次才能命中”。2.3 从线性到树到哈希一条效率递进的路线这一章的结构安排其实很有逻辑先讲最朴素的顺序查找再讲基于有序的折半查找然后讲分块查找做折中接着进入树形结构二叉排序树、平衡二叉树、B树/B树最后讲哈希查找。这条路线就是一部“查找效率进化史”。顺序查找是O(n)不要求有序插入删除方便折半查找是O(log n)但要求有序且顺序存储插入删除代价大分块查找是两者折中块间有序、块内无序二叉排序树在理想平衡时是O(log n)但退化成链表就变O(n)平衡二叉树强制平衡稳定O(log n)B树/B树是多路平衡专门为磁盘这种“一次读一块”的场景设计哈希表则是用空间换时间理想O(1)。理解这条递进线你就不会孤立地记每个结构而是知道每个结构是为了解决前一个的什么痛点而出现的。这是我学这一章最大的收获。3. 核心查找结构逐个拆解与实操要点3.1 顺序查找最笨但最通用的兜底方案顺序查找就是从表的一端开始逐个比较直到找到或者查完。它的ASL在等概率下是(n1)/2时间复杂度O(n)。很多人觉得这太简单没什么好讲的但它有两个别人替代不了的优点第一对表的结构没有任何要求顺序存储、链式存储都行第二不要求有序。实操要点在于“哨兵”技巧。教材里常讲把待查关键字放在数组下标0的位置作为哨兵从后往前查这样循环里就不用每次判断是否越界少一次比较。这个优化在数据量大时是有意义的。我实测过在n10000的顺序查找里加哨兵能省下接近一次比较的开销虽然量级不变但常数优化也是优化。注意顺序查找的ASL公式(n1)/2是在“查找成功且等概率”的前提下成立的。如果查找失败比较次数是n1带哨兵或n不带哨兵考试里经常在这里挖坑。3.2 折半查找有序才是它的命根子折半查找也叫二分查找前提是表必须有序且顺序存储。它的核心操作是每次拿中间元素和目标比小了就往右半区找大了就往左半区找每次排除一半。ASL大约是log₂(n1)-1时间复杂度O(log n)。这里必须讲清楚一个常见误区折半查找的效率高代价是“有序”这个前提。维护有序是要花钱的——每次插入一个元素平均要移动n/2个元素。所以折半查找适合“静态或极少改动”的场景。如果你在一个频繁插入的数据集上用折半查找那维护有序的成本会远远超过查找省下来的时间。判定树是分析折半查找的关键工具。把每次比较的中间元素画成树节点你就得到一棵平衡的二叉判定树树高就是最大比较次数约等于log₂n向上取整。我建议你亲手画一次n11的判定树画完你对ASL的计算就彻底通了比死记公式强得多。代码层面折半查找的边界处理是新手最容易翻车的地方。到底是while(low high)还是while(low high)mid是(lowhigh)/2还是low(high-low)/2这些细节直接决定你的代码是死循环还是漏元素。我的习惯是统一用low high配mid low (high - low) / 2前者保证区间闭合后者防止lowhigh溢出。3.3 分块查找顺序和折半的中间路线分块查找又叫索引顺序查找。它把表分成若干块块内元素可以无序但块间必须有序——也就是第一块的所有元素都小于第二块的所有元素以此类推。再建一个索引表记录每块的最大关键字和起始位置。查找时分两步先在索引表里确定目标在哪一块索引表有序可以折半再在块内顺序查找。它的ASL是两部分之和理想情况下块长取√n时ASL约为√n1比顺序查找的n/2好比折半的log n差。它的价值在于折中插入删除比纯有序表方便查找又比纯顺序快。实操心得分块查找的块长选择很关键。块太长块内顺序查找慢块太短索引表太长索引查找慢。理论上最优块长是√n但实际中还要看数据分布和操作比例。如果插入删除多块可以适当大一点减少索引维护如果纯查块可以小一点。3.4 二叉排序树动态查找的入门结构二叉排序树BST的定义是左子树所有节点小于根右子树所有节点大于根且左右子树也都是BST。它的查找过程就是从根开始比根小往左走比根大往右走。理想情况下树高是log n查找效率O(log n)。但BST有个致命问题它的形态完全取决于插入顺序。如果你按1,2,3,4,5的顺序插入BST就退化成一条只有右孩子的链查找变成O(n)跟顺序查找一样。这就是为什么后面要引入平衡二叉树——就是为了防止这种退化。删除操作是BST里最复杂的分三种情况删叶子直接删删只有一个孩子的节点用孩子顶替删有两个孩子的节点通常用中序前驱或后继替换再删那个前驱/后继。我见过很多人写删除时只处理了前两种遇到第三种就乱套。记住一句话两个孩子的删除本质是转化成删除一个叶子或单孩子节点。3.5 平衡二叉树AVL用旋转换稳定AVL树是最早的自平衡二叉排序树要求任意节点的左右子树高度差平衡因子绝对值不超过1。插入或删除导致失衡时通过旋转来恢复平衡。旋转分四种LL型右旋、RR型左旋、LR型先左后右、RL型先右后左。旋转这块很多人靠背其实理解起来不难。核心就一句话旋转是为了把高的那一边“压”下去同时保持中序遍历顺序不变。你只要记住中序序列必须保持有序旋转的方向自然就推出来了。比如LL型左边太高那就把左孩子提上来当根原根变成右孩子这就是右旋。AVL的查找、插入、删除都是O(log n)代价是每次操作后可能要旋转维护成本比普通BST高。实际工程里AVL用得不如红黑树多因为红黑树的平衡条件更宽松旋转次数更少综合性能更好。但AVL是理解平衡树的最佳入门学明白了再看红黑树会轻松很多。3.6 B树与B树为磁盘而生的多路平衡B树和B树是这一章的进阶内容也是数据库索引的核心。它们的出现是因为磁盘IO的特性一次读一块块内数据读取几乎不花额外时间。所以我们要尽量让树矮一点、每个节点多存点关键字减少磁盘访问次数。一棵m阶B树每个节点最多m个孩子、m-1个关键字除根外每个节点至少⌈m/2⌉个孩子。B树是B树的变种所有关键字都出现在叶子节点叶子节点用链表串起来非叶子节点只做索引。B树的优势是范围查询特别快因为叶子是链式的找到起点后顺着链表扫就行。为什么数据库爱用B树而不是B树两个原因一是B树非叶子节点不存数据同样大小的磁盘块能存更多索引项树更矮二是叶子链表让范围查询和全表扫描效率极高。这个知识点面试高频一定要能说清楚。3.7 哈希查找用空间换时间的极致哈希查找的思路完全不同它不比较而是通过哈希函数直接算出元素该存的位置。理想情况下一次就能找到ASL接近1。但哈希有个绕不开的问题——冲突也就是两个不同关键字算出了同一个地址。处理冲突的方法主要有两类开放定址法线性探测、二次探测、再哈希和链地址法拉链法。线性探测简单但容易产生“堆积”二次探测能缓解堆积但可能探测不到所有位置链地址法把冲突元素挂成链表删除方便实际用得最多。哈希查找的性能取决于三个因素哈希函数是否均匀、装填因子α元素数/表长、冲突处理方法。α越大冲突越多一般控制在0.7到0.75以下。我实测过链地址法在α1时平均查找长度大约1.5而线性探测在α0.75时就已经接近2.5了差距明显。提示哈希表不是万能的。它不支持范围查询也不支持按顺序遍历。如果你的场景需要“找大于某值的所有元素”哈希表帮不了你还得靠树结构。4. 实操过程与核心环节实现4.1 折半查找的完整实现与边界验证我把折半查找的代码完整写一遍重点标注边界处理。假设数组a有序长度为n查找目标keydef binary_search(a, key): low, high 0, len(a) - 1 while low high: mid low (high - low) // 2 if a[mid] key: return mid elif a[mid] key: low mid 1 else: high mid - 1 return -1这段代码的关键点有三个第一low high保证区间闭合当low和high相等时还要比较一次第二mid low (high - low) // 2防止整数溢出虽然Python不会溢出但换成C或Java就必须这么写第三更新时是mid 1和mid - 1不是mid否则会死循环。验证方法很简单拿n1、n2、n3的边界情况各跑一遍再拿目标在第一个、最后一个、不存在的情况各跑一遍。我见过太多人代码写完了不测边界结果考试或面试时被一个n1的用例问倒。4.2 二叉排序树的插入与查找手写流程BST的插入逻辑是从根开始比当前节点小就往左大就往右走到空位就插入。查找逻辑一样只是走到空表示没找到。我用一个具体序列演示依次插入50, 30, 70, 20, 40, 60, 80。插入50成为根30比50小做左孩子70比50大做右孩子20比50小、比30小做30的左孩子40比50小、比30大做30的右孩子60比50大、比70小做70的左孩子80比50大、比70大做70的右孩子。最终这棵树是平衡的查找任何一个元素最多比较3次。但如果换成插入10, 20, 30, 40, 50树就退化成一条右链查找50要比较5次。这就是BST的不稳定性。你可以自己动手画这两棵树对比一下感受会非常直观。4.3 AVL旋转的判定与操作步骤AVL旋转的判定流程是插入后从插入点往上找第一个失衡节点看它是哪种类型。判断依据是失衡节点和它的孩子、孙子的相对位置。LL型做一次右旋RR型做一次左旋LR型先对左孩子左旋再对失衡节点右旋RL型先对右孩子右旋再对失衡节点左旋。以LR型为例假设失衡节点是AA的左孩子是BB的右孩子是C。操作是先对B做左旋让C顶上来再对A做右旋让C成为新的子树根。旋转后中序序列不变但树恢复了平衡。我建议你拿纸笔画三次每次旋转后检查中序序列是否还是原来的顺序检查通过了就说明你旋对了。4.4 哈希表构造与冲突处理实操假设关键字集合是{19, 14, 23, 1, 68, 20, 84, 27, 55, 11}哈希函数用H(key) key mod 13表长取13。我实际算一遍19 mod 13 614 mod 13 123 mod 13 101 mod 13 1冲突68 mod 13 320 mod 13 784 mod 13 6冲突27 mod 13 1冲突55 mod 13 3冲突11 mod 13 11。用线性探测处理冲突1放在位置114已经在1往后找到位置2放184本来该放619在6往后7有208空放827该放11、2被占3有684空放455该放33到7都被占8有849空放9。最终表里每个位置的情况你都能推出来。用链地址法的话位置1挂14→1→27位置6挂19→84位置3挂68→55其余各占各位。链地址法的ASL计算是把每条链的长度平方和除以元素数再调整具体公式教材有但理解上就是链越短越好。5. 常见问题与排查技巧实录5.1 折半查找死循环与漏查的排查折半查找最常见的两个bug死循环和漏查。死循环通常是因为更新low或high时没有1/-1比如写成low mid当区间只剩两个元素且目标在右边时mid永远等于low区间不缩小。漏查通常是因为循环条件写成low high当区间只剩一个元素时直接退出没比较那个元素。排查方法拿n2的数组目标分别是第一个和第二个元素手动模拟你的代码看能不能正确返回。如果两个用例都过基本就没问题。这个技巧我用了很多年比看代码快得多。5.2 BST退化的识别与规避BST退化没有明显的报错它只是变慢。识别方法是看树高如果树高接近节点数n说明退化了。规避方法有两种一是插入前打乱顺序但很多场景做不到二是直接用平衡树比如AVL或红黑树。实际工程里如果你需要有序的动态查找结构别自己写BST直接用语言内置的有序容器比如C的map、Java的TreeMap它们底层都是红黑树。5.3 哈希冲突堆积的观察与调整线性探测的堆积问题表现为某些区域连续被占导致后续插入和查找都要探测很多次。观察方法是统计探测次数的分布如果某些位置的探测次数明显偏高说明堆积严重。调整方法有三种换更好的哈希函数、增大表长降低装填因子、改用链地址法。我一般优先考虑增大表长因为改哈希函数可能影响已有数据改冲突方法改动更大。5.4 常见问题速查表问题现象可能原因排查思路解决方法折半查找死循环low/high更新未收缩用n2手动模拟改为mid±1折半查找漏查循环条件用检查边界用例改为BST查找变慢树退化成链计算树高改用平衡树哈希查找变慢装填因子过高算α元素数/表长扩容或改冲突方法AVL旋转后中序乱旋转方向搞反检查中序序列重新判定LL/RR/LR/RLB树范围查询慢叶子未串链检查叶子指针补上叶子链表5.5 几个教材不会明说但很实用的经验第一ASL的计算一定要分清“成功”和“失败”。成功的ASL是找到元素的平均比较次数失败的ASL是找不到时走到空位的平均比较次数两者公式不同考试经常分开问。第二折半查找的判定树一定是平衡的但平衡二叉树不一定是折半查找的判定树。前者是查找过程的描述后者是一种数据结构别混。第三哈希表的ASL和装填因子直接相关考试里如果给了α直接用公式算别傻乎乎地一个个模拟。链地址法成功ASL约1α/2线性探测成功ASL约(11/(1-α))/2这些公式要记。第四B树的阶m和节点关键字数的关系是最多m-1个关键字最少⌈m/2⌉-1个。这个“减一”很多人记错画一棵3阶B树验证一下就记住了。第五实际写代码时能用内置的有序结构就别自己实现平衡树。自己写AVL或红黑树出错概率极高除非是学习目的或者有特殊需求。6. 我个人在实际操作中的体会学查找这一章最大的坑不是某个结构难而是容易把它当成一堆孤立的知识点去背。我当初就是一个个结构单独记结果考试一综合就懵。后来我换了个思路把这一章看成一条“效率进化线”每个结构都是为了解决前一个的某个缺陷而出现的。顺序查找不要求有序但慢折半查找快但要求有序且插入贵分块查找折中BST动态但会退化AVL强制平衡但旋转多B树为磁盘优化哈希用空间换时间但不支持范围查询。你顺着这条线走每个结构的存在理由就都清楚了。另一个体会是ASL这个指标一定要亲手算几遍。我见过太多人公式背得滚瓜烂熟给一个具体序列让他算ASL就卡壳。找几个典型序列顺序的、折半的、哈希的各算一遍算完你对这些结构的理解会上一个台阶。最后分享一个小技巧如果你在准备面试把“为什么数据库索引用B树不用哈希”这个问题彻底想清楚基本就能覆盖查找这一章80%的高频考点。答案的核心就是B树支持范围查询和顺序遍历且树矮IO少而哈希不支持范围查询。把这个讲透面试官会觉得你是真懂而不是背的。
阅读完成 · 觉得有帮助？
