很多年前我刚开始学数据结构的时候总觉得查找算法是个“既简单又没用”的东西——简单在代码不过几行没用在日常开发里随手调个indexOf就完事了。直到后来在工作中排查一个线上性能问题才发现一套几百万行的业务配置表每次加载都要做线性扫描CPU占用率居高不下才意识到所有数据库索引、缓存加速、搜索框提示本质上都在做同一件事在一个集合里尽快找到目标。这篇文章就围绕线性表上最经典的四种查找算法——顺序查找、二分查找、插值查找、分块查找把它们的思路、推导、代码和真实工程场景完整串一遍。内容覆盖从零基础到面试拔高的需求刚学数据结构的人可以照着代码理解原理准备笔试面试的人可以拿ASL平均查找长度推导和时间复杂度分析当复习提纲已经在写业务代码的人也能从选型对照里找到“我到底该用哪一种”的判断依据。整篇文章没有花哨的框架就是实打实地把每种算法的“为什么这么做”讲透。1. 查找算法里的两把尺子ASL与存储载体在讲具体算法之前先把两个基础概念钉死后面所有比较都离不开它们。第一把尺子是ASL中文叫平均查找长度。它衡量的是“为了找到目标平均要比较多少次”。假设查找表里有n个记录第i条记录被找到需要比较ci次那么查找成功的ASL就是ASL (c1 c2 ... cn) / n这个公式看着简单但它把算法的效率直接量化了。比如一个无序线性表顺序查找第1个元素只需比较1次第2个元素需要2次第n个元素需要n次所以成功查找的ASL (12...n)/n (n1)/2。这个数字告诉我们在100万条数据里用顺序查找平均要比较50万次这个代价在性能敏感的场景里是不可接受的。第二把尺子是存储载体。线性表有两种物理存储方式顺序表数组和链表。这是很多人学查找算法时忽略的关键点。二分查找要求能直接跳到中间位置也就是O(1)随机访问只有数组能做到链表要访问第mid个节点必须从头遍历过去每次“跳中”都是O(n)时间说白了链表上做二分查找的每一步都在付出线性代价整体效率退化成O(n log n)还不如顺序查找。还有一个概念容易混淆主关键字和次关键字。主关键字可以唯一标识一条记录比如学号、身份证号、订单号次关键字则可能对应多条记录比如“年龄25”可能命中几百个人。后文讨论的“查找”默认指主关键字查找也就是搜索结果唯一或者只需要返回第一条记录。把这两把尺子放在一起再看四种算法的演进逻辑就很清晰了顺序查找不关心数据有没有序代价是O(n)比较二分查找利用顺序表的有序性把比较次数压到O(log2 n)插值查找再把二分的“机械折半”改成“智能比例定位”在数据分布均匀时进一步逼近O(log log n)分块查找则是折中方案不需要全表有序只要块间有序、块内随意换来的是插入删除的灵活性。这四条路本质上就是在“数据的有序程度”和“查找的效率”之间做交换。2. 顺序查找无约束数据的兜底方案顺序查找的代码几乎所有人都能写出来从第一个元素开始逐个比直到找到目标或遍历完整个表。不过教科书里有个优化版本用哨兵位省掉“判断数组越界”的步骤。先看最常规的实现。// a[1..n]存储数据a[0]留着做哨兵位 int seqSearch(int a[], int n, int key) { for (int i 1; i n; i) { if (a[i] key) return i; // 找到返回下标 } return 0; // 没找到 }每次进入循环体都要先判断i n再判断a[i] key一个循环做了两件事。哨兵版本的做法是把key先存到a[0]位置然后从n往前扫这样省掉了i n的越界判断。int seqSearch(int a[], int n, int key) { a[0] key; // 哨兵 int i n; while (a[i] ! key) { i--; } return i; // 返回0表示没找到 }这个优化本质上把“两个条件判断”降成“一个条件判断”现代编译器有分支预测和循环展开性能差距在n很大的时候依然可观。我实测过在一个1亿量级的整数数组上跑200次查找哨兵版大约比普通版快10%~15%。还有人说“这不就是拿空间换时间嘛”严格讲不是空间换时间——a[0]本来就在数组里你把它的值换成了key只多占用了一个逻辑位置没有额外分配堆内存。顺序查找的时间复杂度固定是O(n)查找成功时ASL (n1)/2查找失败时一定是n次比较差一个哨兵位。它的优缺点非常分明特性说明数据要求无序有序都能查对数据零约束存储要求顺序表、链表都支持链表也能用平均查找长度(n1)/2数据量一大就吃力优点实现简单、插入删除极方便、无额外空间缺点数据量大时比较次数太多那它到底还有没有应用场景有而且很常见。第一种场景是小数据量比如某个配置项列表只有几十条你从头扫到尾消耗可以忽略不计完全没必要先建索引再二分。第二种是无顺序要求的链表链表本身不支持随机访问强行做二分反而不划算顺序查找反而是最自然的选择。第三种是动态插入频繁的散表数据不断在尾部追加而且无序这时你还想保持“能查”顺序查找就是兜底方案。我自己的一个教训是不要因为顺序查找“低级”就轻视它很多线上问题恰恰是因为没有在最简单场景用它反而引入了复杂的缓存或索引结构增加维护成本。工程判断里简单和正确是优先级的起点。3. 二分查找有序表上的折半数学二分查找的思想一句话就能说清每次拿目标值和中间元素比较小于就往左半区找大于就往右半区找区间范围每次缩小一半直到找到或区间为空。它依赖两个前提数据必须有序存储必须是顺序表。哨兵优化那套在二分里没有意义关键难点全在边界条件的写法上。给出一个标准的左闭右闭写法int binarySearch(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; } else if (a[mid] key) { left mid 1; // 目标在右半区 } else { right mid - 1; // 目标在左半区 } } return -1; // 没找到 }这段代码里有几个细节值得反复琢磨。第一个是mid left (right - left) / 2而不是mid (left right) / 2。后者在left和right都很大的时候可能整型溢出比如left15亿right15亿直接相加会超过int上限前者则完全避开了这个问题。第二个是while (left right)的退出条件。这里意味着最后一个元素也要参与判断区间为空时循环退出如果写当区间里只剩一个元素时会少一次比较容易漏判。第三个是left和right的更新必须加上或减去1因为mid已经被排除在外。很多人写错二分基本都是这几个地方互相配错了。为什么必须在顺序表上做二分回到指针跳转的代价问题。数组知道首地址mid位置可以直接用偏移量算出来O(1)跳转链表每次“折半”都要从头部或当前节点走几步才能到mid一次跳转就是O(n)的遍历那么每层比较都要花n步整体复杂度变成O(n log2 n)比顺序查找的O(n)还要差所以链表中做二分完全不划算。二分查找的效率非常好查找成功时ASL约等于log2(n1)-1最坏情况下比较次数也不超过⌊log2 n⌋1。n100万时顺序查找平均50万次二分查找大约只要20次这就是数量级的差距。不过二分查找的“阿喀琉斯之踵”在于维护有序表的成本太高。假如你有一个有序数组每次插入一条新记录平均要移动后面一半的元素插入一次就是O(n)。如果数据是静态的比如字典表、省份编码表、历史归档数据建一次序然后反复查二分是最优选但如果数据一直在增删为了保持“有序”付出的代价可能超过查找节省的时间。这时候就要考虑后面讲的分块查找或者干脆用平衡二叉搜索树、跳表这些支持动态维护的结构。4. 插值查找给二分查找装上一个“斜率”二分查找有一个“笨”的地方不管目标值在哪个区间它都机械地取中点。比如在一个从1到100000均匀递增的数组里找目标值2二分查找第一次会跳到50000然后2500012500……要一步一步缩到左端效率并不理想。人类查字典不会这样做——翻“安”字时你会把书翻到前几十页翻“张”字时你会直接翻到偏后的位置。插值查找就是把人类翻字典的比例直觉算法化。它的核心变化只有一行原来mid (left right) / 2现在改成按目标值在区间中的“位置比例”来确定mid。假设数组a[left]到a[right]是递增的目标key在这两个值之间那么一个合理的比例估算就是mid left (key - a[left]) / (a[right] - a[left]) * (right - left)这个公式很好理解key - a[left]表示目标值相对于区间左端点多远除以a[right] - a[left]就是它在整个数值区间内的相对位置再乘以下标区间的长度就得到了一个按比例推算出来的下标。前面等分是均匀1/2这里是动态比例所以也叫“按比例查找”。给一个Python实现方便看清逻辑语言无所谓思路是通用的。def interpolation_search(a, n, key): left, right 0, n - 1 while left right and a[left] key a[right]: # 防止除零 if a[left] a[right]: return left if a[left] key else -1 # 按比例估算 mid pos left (key - a[left]) * (right - left) // (a[right] - a[left]) # 下标可能越界加一层保护 if pos left or pos right: break if a[pos] key: return pos elif a[pos] key: left pos 1 else: right pos - 1 return -1插值查找的前提比二分苛刻数据不仅要有序数值分布还要均匀。连续递增的整数、按时间戳排列的记录、均匀分布的编号等是理想场景如果数据分布极不均匀比如大部分元素集中在某个小区间那比例估算会频繁偏差mid反复跳到区间的两端最坏情况会退化成O(n)的比较次数还不如老老实实二分。复杂度方面均匀分布的前提下插值查找平均比较次数约为O(log log n)。这个式子需要一个直观感受n1亿时二分查找约27次插值查找平均不到5次差距明显。但注意“平均”两个字它依赖数据分布的统计性质不保证最坏情况。因此我的建议是只有你对表内数据的数值特征有把握知道它近似均匀才值得用插值查找否则写二分更稳妥。实际工程里还有一个容易踩的坑a[right] a[left]时除数为0必须单独处理目标值超出区间范围时比例公式会算出越界下标也要加判断。这些边界看起来不起眼真上线跑数据分布极端的表时分分钟变段错误。5. 分块查找用索引表换来更新自由最后讲分块查找它的设计思路我觉得是四种算法里最有智慧的一个。前面二分查找对有序性的要求是“全局有序”这在实际业务中非常奢侈。分块查找把这个要求降级为块与块之间有序块内部可以任意无序。再额外建一张索引表索引表里记录每一块的最大关键字和块的起始位置因为块间有序索引表必然有序于是可以在索引表上做二分确定目标可能落在哪一块最后在块内用顺序查找扫一遍。具体过程三步走将长度为n的线性表分为m块每块长度约s最后一块可以不满。建一张索引表表里每一项是(该块最大关键字该块在原始表里的起始下标)。查找时先在索引表上二分查找找到目标值应当落入的块再进入该块从头到尾顺序扫描。平均查找长度可以拆成两部分查索引表的花费加上查块内的花费。ASL ≈ log2(m1) (s1)/2这里m n/s。以n10000为例如果s100索引表有100项先二分索引表约7次再在块内最多100次、平均50次总平均约57次。顺序查找平均5000次二分查找全表有序平均约13次。分块查找比顺序快得多比二分慢但它换来一个关键能力块内无序意味着插入和删除非常方便。你会想块大小s怎么取最合适把ASL的表达式看成s的函数ASL ≈ log2(n/s 1) (s1)/2。第一项随s增大而变小第二项随s增大而变大一减一增之间存在一个极小值点。求导后可得最优的s大约在√n附近。工程经验也印证这一点当s取√n时索引表规模大约是√n整体查找次数在2√n这个量级。10000条数据时s100索引表100项平均查找百次以内空间开销也很小性价比很高。分块查找的空间复杂度是O(n/s)即额外多一张索引表。相比二分查找的O(1)额外空间它多了一点开销但换来的是更友好的动态性。实际工程里它的影子无处不在数据库的表分区、文件系统目录索引、内存页表的二级索引都是“先分层索引缩小范围再在局部线性扫描”的组合思想。下面是一个带有简单索引表的分块查找示例用C语言描述核心逻辑。typedef struct { int maxKey; // 块内最大关键字 int start; // 块在原始表中的起始下标 } IndexNode; // blockSize 等于 sqrt(n) 左右块数 (n blockSize - 1) / blockSize int blockSearch(int a[], int n, IndexNode index[], int blockSize, int key) { // 在索引表上二分确定所在块 int low 0, high (n blockSize - 1) / blockSize - 1; while (low high) { int mid (low high) / 2; if (index[mid].maxKey key) { high mid - 1; } else { low mid 1; } } int blockIdx low; // 找到的块号 int end (blockIdx 1) * blockSize; if (end n) end n; // 在该块内顺序查找 for (int i index[blockIdx].start; i end; i) { if (a[i] key) return i; } return -1; }这里有个容易理解偏差的地方索引表二分查找的写法要“找第一个maxKey key的块”而不是“找maxKey恰好等于key的块”。因为索引表存的是“块的最大值”key不一定正好等于某个块的最大值它只是落在某个块的取值范围内。写代码时这一点一定要想清楚。6. 选型对照从复杂度公式到工程场景四种算法讲完之后把它们放在同一张表里做一次整体对照选型的时候就清晰多了。算法数据要求存储载体成功ASL最坏查找次数额外空间动态性顺序查找无序/有序均可顺序表、链表(n1)/2nO(1)很好尾部插入极方便二分查找全局有序顺序表log2(n1)-1⌊log2 n⌋1O(1)差保持有序需要大量移动插值查找有序且数值均匀顺序表约log2 log nn分布差时退化O(1)差同二分分块查找块间有序、块内无序顺序表索引表log2(n/s1)(s1)/2约√n量级O(n/s)较好块内插入删除方便这张表背下来不难但真正做技术选型时要看的是具体的访问模式。我一般按这几种场景来决策静态数据查询频繁优先二分查找。比如一个只读的编码映射表启动时加载一次之后被接口高频查询有序数组加二分是性能和内存开销的平衡点。数据分布均匀查询极频繁可以试插值查找。比如按时间戳递增的记录、连续编号的设备表这类数据天然满足均匀分布插值查找可以把平均查找次数压到个位数。但上线前务必做一次分布校验别拍脑袋直接用。数据持续增多查询不能太慢分块查找或者更进一步用跳表、B树这类动态索引结构。分块查找的优势在于既不用维护全局有序又能把查询规模控制在√n量级。适合那种“查询多、插入也多”的中间态场景。数据无序量小或链表存储直接顺序查找。别为了用二分而去复制一份数组带来额外的内存和维护成本。还有一个容易被面试官问到的坑有序链表上快速找到目标的方案是什么答案是二分查找做不了可以改进成“索引”思路把链表节点分层建索引这就是跳表的基本原理。跳表后面可以单独写一篇今天的四种算法其实已经把“用索引换时间”的思想铺垫完了——分块查找就是跳表和B树的朴素祖先。把四条线串起来的那点经验最后说点个人体会。学习这四种查找算法最好的方式不是只背公式和复杂度而是手写一遍代码并画出查找过程。我在刚学的时候做过一个可视化练习把1到1000的有序数组打印出来然后手动模拟二分和插值的每一步标出mid的位置看它们如何从两端快速逼近目标。这个过程做完以后在代码里写二分就像写循环一样顺手。一个小技巧写二分查找出问题时第一步先检查“区间变化后是否漏掉元素”。如果你用的左闭右闭却忘了在边界上加减1大概率会死循环或者错过边界值可以写完后用几个特殊用例自测比如n1、n2、目标在两端、目标不存在这四个用例跑一遍80%的边界问题都能暴露出来。另外真实系统里查找算法很少是单枪匹马出现的。我参与过的一个配置服务最外层用分块索引缩小范围块内用顺序查找兜底结果发现块内数据量越来越小就把顺序查找换成了插值查找整体查询耗时又降了一截。这四种算法像是同一根藤上长出来的四个果实把它们放在一起理解再遇到新场景时就不会只会背答案了。