数据结构这门课里顺序表的查找算是最容易被低估的一个知识点。刚学的时候觉得无非就是遍历比一比、或者排好序之后折半找一找代码写起来也没几行。但等你真正在工程里处理上万条、上百万条记录或者在算法题里被各种边界条件折磨过之后才会意识到查找这件事的细节深度远比教材里的伪代码丰富得多。哪怕是看似简单的顺序查找也存在哨兵优化自组织表这些教科书后边的小字内容而二分查找则更是出了名的思路一分钟写对一小时。这篇博文我想结合自己实际写代码和排查问题的经验把顺序表上的两种基础查找——顺序查找和二分查找——从原理到坑点彻底捋一遍给正要学数据结构的人一条更平滑的上手路径也给已经在写业务代码的朋友一些值得回看的细节。1. 顺序查找先看清楚它的性能基线再谈优化1.1 最朴素的实现以及平均查找长度是怎么算出来的顺序查找又称线性查找的思路没有任何玄学从顺序表的第一个元素开始挨个和目标值比较直到找到为止。用 C 语言描述就是下面这副样子int seqSearch(int arr[], int n, int key) { for (int i 0; i n; i) { if (arr[i] key) { return i; // 找到返回下标 } } return -1; // 没找到 }这是绝大多数人第一次接触查找时写的版本。它把顺序表当成一段连续内存上的数组来遍历逻辑简单到不需要额外解释。但教材里紧接着就会引入一个概念平均查找长度ASLAverage Search Length。为什么这个概念重要因为它是衡量查找算法效率的第一把尺子。假设你要查找的记录在表中是等概率出现的即每条记录被查到的概率都是 1/n。那么查第 1 个元素需要比较 1 次查第 2 个元素需要比较 2 次……查第 n 个元素需要比较 n 次。于是ASL(成功) (1 2 … n) / n (n 1) / 2这个公式的意思是在等概率成功查找的前提下顺序查找平均要比较大约一半的元素。如果查找经常失败那更惨因为必须遍历完整个表才能确认没有这个元素比较次数恒为 n 1多出来的一次是用于判断越界。我见过不少初学者在分析算法复杂度时只记结论不推导过程。其实这个推导特别值得亲手做一遍因为理解了成功和失败两种情况下比较次数不同才会明白后面哨兵优化的意义到底在哪里——它优化的不是成功情况下的比较次数而是失败情况下每次循环里那个额外的越界判断。1.2 哨兵位优化少写一次越界判断就能省下大量指令在顺序查找的朴素版本里for 循环的每一轮都要执行i n这个判断。当表很长、且查找频繁失败时i n会被执行 n1 次。这个判断本身成本不高但量变引起质变在追求极致性能的底层代码里它是可以省掉的。办法就是设置哨兵sentinel。具体做法是把目标值 key 临时放到顺序表末尾的空位上然后从表尾开始往前找。由于末尾一定存在一个 key所以查找过程必定会命中。如果命中位置正好是哨兵位说明原表中根本没有这个元素。int seqSearchWithSentinel(int arr[], int n, int key) { int i n; arr[n] key; // 把 key 放在哨兵位要求数组实际容量 n1 while (arr[i] ! key) { i--; } return i n ? -1 : i; // 返回 n 表示没找到 }这个版本里while 循环只判断arr[i] ! key一个条件少掉了每次比较下标是否越界的判断。数据量一大省下的就是 n 次条件判断的开销。代价是数组必须预留哨兵位并且多一次写入操作。我在实际项目里用这个技巧的场景是在一个内存里维护的极简哈希桶冲突链上做顺序探测。当时每次读请求都要在一个小数组里扫描十几个元素把 n1 次越界判断减掉之后虽然单次节省的纳秒数微乎其微但作为热路径hot path上的优化累积效果在压测曲线上一眼就能看出来。顺带说一句这种用空间换掉高频分支判断的思路在很多高性能代码里都会反复出现值得形成肌肉记忆。1.3 什么时候顺序查找反而是最优解很多初学者容易形成一种错觉学了二分查找之后顺序查找就该被淘汰了。事实完全不是这样。顺序查找在现代工程里的生存空间比想象中大得多因为它有几张二分查找给不了的牌第一数据无序。二分查找的前提是数据有序而很多业务场景中的数据天然就是无序的为了查找去维护有序性的成本可能远高于顺序查找本身的成本。第二数据量小。当 n 很小的时候比如几十个元素顺序查找的线性扫描可能比二分查找更快。原因后面会展开说简单讲就是现代 CPU 对顺序内存访问实在太友好了简单的循环分支预测命中率极高。第三插入删除频繁。顺序表本身不擅长插入删除但如果换成链表形态顺序查找仍然是唯一可行的基础查找方式——链表无法随机访问二分查找的思想在链表上根本施展不开。所以我的经验是遇到在数组/顺序表里找东西的需求先判断数据是否有序、规模大概多少再决定用什么算法而不是一上来就上二分。这条选型思路在第 4 章还会继续深化。2. 二分查找一份看似简单、极容易写错的标准答案2.1 循环不变量是唯一需要盯住的东西二分查找也叫折半查找的思想一句话就能说完在一个有序的顺序表里每次拿中间元素和目标值比较根据比较结果把搜索区间砍掉一半。但为什么这个算法从 1946 年提出到 1962 年才有人写出第一个完全正确的实现因为边界怎么处理这一件事折磨了计算机科学家十几年也继续折磨着今天每一位刷 LeetCode 的开发者。问题出在哪儿出在很多人写二分时靠感觉而不是靠逻辑维护搜索区间。比如下面这个最经典的写法int binarySearch(int arr[], int n, int target) { int low 0, high n - 1; while (low high) { int mid low (high - low) / 2; if (arr[mid] target) { return mid; } else if (arr[mid] target) { low mid 1; } else { high mid - 1; } } return -1; }这段代码能正常工作靠的是它维护了一个非常清晰的循环不变量目标值 target 如果存在则一定落在闭区间 [low, high] 内。初始时low 0, high n - 1整个数组都在区间内不变量成立。每一轮循环如果arr[mid] target说明 target 只可能出现在 mid 右边于是把 low 推进到 mid 1新区间仍然是可能包含 target 的完整候选区间反之亦然。当low high时区间为空target 必然不存在。写二分时最容易犯的错误就是循环条件、low/high 的更新方式和区间定义这三者自相矛盾。比如你用闭区间定义却在arr[mid] target时写low mid而不是 mid 1那么当 low 和 high 相邻时mid 可能一直等于 lowlow 永远推不动程序就陷入了死循环。这不是粗心而是你心里对区间边界的定义不清晰。2.2 三种常见写法的取舍我建议你至少吃透一种二分查找在细节上有很多流派常见的有三种区间定义闭区间[low, high]、左闭右开[low, high)、以及排除法式的写法。初学者不需要全都精通但至少要把一种写法焊死在脑子里知道每一步为什么这么写。我自己的习惯是左闭右开它在处理变体问题时心智负担更低int binarySearchLeftOpen(int arr[], int n, int target) { int low 0, high n; // 搜索区间 [low, high) while (low high) { int mid low (high - low) / 2; if (arr[mid] target) { low mid 1; // mid 排除且 mid target所以新区间 [mid1, high) } else if (arr[mid] target) { high mid; // mid 排除新区间 [low, mid) } else { return mid; } } return -1; }注意这里的边界更新因为区间是左闭右开所以排除 mid 时右边界直接写成high mid就行不需要减一。这个对称性非常好记也不容易出现减一导致区间跳过元素的问题。如果让我给一条最实际的建议那就是不要一会儿用闭区间、一会儿用左闭右开。每次切换都要重新推导边界逻辑出错概率极高。选定一种写清楚循环不变量然后在这个基础上吃透变体题。2.3 为什么二分查找的时间复杂度是 O(log n)以及 ASL 的直观理解二分查找为什么快因为每比较一次搜索范围就缩小一半。从 n 个元素缩小到 1 个元素最多需要比较多少次答案是 log2(n) 次精确说是 ⌊log2(n)⌋ 1。相比顺序查找的线性增长对数增长在数据量变大时优势是指数级别的。比如 n 1024 时顺序查找最多比较 1024 次二分查找最多比较 11 次n 扩大一倍到 2048顺序查找的比较次数也跟着翻倍二分查找只多比较 1 次。这就是对数级两个字的真实含义。从平均查找长度角度等概率成功查找时二分查找的 ASL 约等于 log2(n1) - 1。这个数值比顺序查找的 (n1)/2 低了好几个数量级。不过别急着背公式更有价值的理解方式是把它看成一棵判定树每次比较产生两个分支大了往右、小了往左整个查找过程就是从树根走到某个叶子节点路径长度就是比较次数。一棵高度为 h 的满二叉树最多容纳 2^h - 1 个节点反过来n 个节点构成的判定树高度就是 ⌈log2(n1)⌉。理解了这层对应关系二分查找的时间复杂度就不是需要死记的结论而是顺理成章的推导结果。同时也要清醒认识到二分查找的快建立在两个前提上——数据必须有序、必须能用 O(1) 时间随机访问任意位置的元素。第二个前提意味着它只能用在顺序表数组上链表不行。这也是为什么后面讲 B 树的时候会说数据库索引本质上是把二分查找从二叉变成了多叉因为磁盘这种存储介质上随机访问的代价实在太大了需要降低树的高度来减少读盘次数。3. 二分查找的常用变体这才是工程里的高频需求3.1 找第一个等于 target 的下标和最后一个等于 target 的下标工程里有一个比找到任意一个 target更高频的需求在有序数组中找到第一个等于 target 的位置或者最后一个等于 target 的位置。典型场景比如统计某个分数段内有多少人、查日志里某个错误码第一次出现的行号。最自然的做法是先用二分找到一个 target然后向左/向右线性扩展。这个做法的问题在于如果数组里 target 非常多比如有一万个相同的值线性扩展就又变回了 O(n) 复杂度完全失去了二分查找的意义。正确的姿势是把等于的判断拆开让二分查找自己在边界处停下来。先看第一个等于 target的写法int lowerBound(int arr[], int n, int target) { int low 0, high n; while (low high) { int mid low (high - low) / 2; if (arr[mid] target) { low mid 1; } else { high mid; // arr[mid] target 时high 收缩到 mid } } return low; }这个函数返回的是第一个不小于 target 的下标也就是标准库里的 lower_bound。如果数组里存在 targetlower_bound 返回第一个等于 target 的位置如果不存在返回第一个大于 target 的位置。所以第一个等于 target的完整逻辑就是int pos lowerBound(arr, n, target); if (pos n arr[pos] target) { return pos; } return -1;而最后一个等于 target的位置可以借助 upper_bound第一个大于 target 的下标再减一得到。upper_bound 的写法几乎一样只是判断条件从arr[mid] target变成arr[mid] targetint upperBound(int arr[], int n, int target) { int low 0, high n; while (low high) { int mid low (high - low) / 2; if (arr[mid] target) { low mid 1; } else { high mid; } } return low; }这类边界判断看起来只是改了一个符号实际写的时候特别容易搞混。我自己的记忆方法是盯住一个问题我到底要排除哪些元素lower_bound 排除严格小于 target 的元素upper_bound 排除小于等于 target 的元素。想清楚排除对象条件就不会写反。3.2 找插入位置lower_bound 和 upper_bound 的另一层价值除了查找元素二分查找还经常用来找位置。比如维护一个有序数组需要插入一个新元素并保持有序就得先算出插入位置或者在一个有序数组里需要知道小于等于 target 的元素有多少个也需要一个位置下标。这时候 lower_bound 和 upper_bound 的价值就彻底体现出来了lower_bound返回的 low就是如果要把 target 插入数组且保持有序target 应该放的位置upper_bound(arr, n, target) - lower_bound(arr, n, target)的值就是数组中等于 target 的元素个数。后者是一个特别实用的技巧。比如你在处理一个有序的用户积分列表想知道 1000 分这个档位上有多少人一行代码就能算出来时间复杂度 O(log n)。我自己以前在做类似统计需求时第一反应是先遍历一遍数个数后来才意识到用两个二分查找边界在数据量大时节省的时间非常可观。这种二分查位置的思路还能扩展到更抽象的二分答案问题上。典型例子是给定一个单调函数 f(x)求满足 f(x) target 的最小 x。这时候不需要数组有序只需要保证函数值关于 x 单调即可。比如求平方根、求有序数组中的极小值、旋转数组中的最小值本质上都是二分思想在值域上的应用而不是在下标上。3.3 旋转数组里的二分一个思维体操但别只会背结论所谓旋转数组是把一个有序数组从某个位置切一刀把前半部分挪到后面去比如[4,5,6,7,0,1,2]就是[0,1,2,4,5,6,7]旋转后的结果。在这种数组里查找 target仍然是二分能解决的问题但关键在于判断当前 mid 落在哪一段有序区间里。思路是虽然整个数组不是有序的但总有一半是严格有序的。每次比较arr[low]和arr[mid]如果arr[low] arr[mid]说明左半段有序否则说明右半段有序。然后根据 target 是否落在这段有序区间内决定下一次搜索去哪一半。这类题在算法面试中出现频率很高但我的建议是不要死记旋转数组的二分代码而是把它当成一个检验自己是否真正理解区间收缩逻辑的习题。如果你能把普通二分查找的循环不变量推导清楚旋转数组的变体也只是多了一个分段判断的条件而已。死记硬背的结果是换一个变形题就懵理解了本质之后万变不离其宗。4. 工程选型顺序表查找在不同数据场景下的真实代价4.1 数据有序就无脑二分真不一定在业务代码里很多人看到数组、有序、查找这三个条件第一反应就是写二分。我必须泼一盆冷水数据量小的时候二分查找经常不是最优解。原因是现代 CPU 对内存的访问模式极其敏感。顺序查找访问的是连续内存地址CPU 的缓存行cache line一次就能加载相邻的多个元素而且这种线性访问模式对硬件预取器prefetcher极度友好——你还没访问到后面的元素CPU 已经提前把它们加载进缓存了。而二分查找每次跳到一个看似随机的位置虽然理论上只比较 O(log n) 次但每一次跳转都可能触发一次缓存未命中cache miss这个代价比比较一次数组元素大得多。所以在 n 很小的场景比如 n 64甚至 n 32顺序查找的线性扫描经常能跑赢二分查找。Java 标准库里的Arrays.binarySearch在内部也不是直接从区间中间开始比较而是对不同长度的数组做了一些优化处理。这不是标准库开发者在炫技而是他们在大量基准测试中发现小数组线性扫描更快这个反直觉的事实。我在自己做过的一个内存数据库模块里实测过在 32 个元素的缓存行内做精确查找线性扫描比二分查找快 20% 到 40%。原因就是扫描每次都命中同一批缓存行而二分查找会在几个缓存行之间跳来跳去。所以工程选型的第一个原则是用数据说话别用复杂度空想。4.2 缓存、分支预测与基准测试从理论到实践的最后一公里要理解上面这个结论需要先建立两个底层概念。第一个是缓存行。CPU 不会一个字节一个字节地从内存读数据而是以固定大小通常是 64 字节为单位读取这就是一个缓存行。顺序扫描数组时第一个元素的加载会把后面十几个元素一起带进缓存后续访问全都是缓存命中而二分查找第一次访问中间元素第二次访问中间元素左边或右边的某个位置这两个位置往往不在同一个缓存行里每次都得到内存里重新取。第二个是分支预测。现代 CPU 有很深的分支预测流水线遇到 if 语句时会猜测走哪条分支。顺序查找的比较结果往往具有某种规律性比如前面若干次都不相等最后一次才相等CPU 的预测器能学出这个规律而二分查找每次跳向哪一半完全取决于数据预测器很难猜准猜错一次就要清空流水线白白损失十几个时钟周期。把这两点合起来你就会明白为什么小数据量线性扫描更快——因为顺序查找牺牲了比较次数但换来了极端友好的内存访问模式和分支预测二分查找节省了比较次数却要为每次随机访问付出额外的缓存和流水线代价。两者各有胜负真正的分水岭在哪里取决于具体硬件和数据规模。所以负责任的做法是写个小基准测试在自己的目标环境上实测。这里给一个简单的测试思路#include stdio.h #include time.h // 两个函数seqSearch 和 binarySearch // 在随机生成的有序数组中对同一组查询分别调用统计总耗时测试时要注意关闭编译器优化或确保结果被使用并且多跑几轮取中位数。我见过很多人在 benchmark 上吃亏要么被编译器把整个循环优化掉了要么只跑一次导致误差巨大。排序算法、查找算法这类微基准测试没有一个标准的测试环境很容易得出完全相反的结论。4.3 从顺序表查找延伸到 B 树、B 树的必要一步顺序表上的查找算法其实只是查找这个庞大主题的第一站。顺着二分查找每次砍掉一半的思路继续往下走自然会走到树形查找二叉查找树把二分查找的判定树显式地建出来每次查找从根节点往下走而 B 树、B 树则是为了让树更适合磁盘存储把二叉变成多叉让树的高度更低从而减少读盘次数。顺序表查找和这些树形结构的关联点在于B 树的每个内部节点本质上就是一个有序的键数组在这个数组内部查找时用的仍然是二分查找或顺序查找。所以顺序表的查找绝不是一个孤立的知识点它是一切查找结构的原子操作。从工程角度看这个延伸的意义是当你面对百万级数据、内存放不下、需要磁盘 IO的场景时就别再纠结顺序表上的二分查找了那只是入门练习真正的答案大概率在数据库索引或类 B 树结构中。反过来如果你连顺序表上的二分边界都理不清直接跳到 B 树去学m 阶 B 树中的查找大概率会被各种节点的关键字分布绕晕。基础打牢才有可能在高阶结构里游刃有余。5. 教科书不会告诉你的坑以及我的排查思路5.1 死循环是怎么悄悄出现的二分查找最常见的 bug 就是死循环而且这个 bug 特别隐蔽——你看代码逻辑每一句都像是对的但程序就是停不下来。我见过无数次初学者对着代码发呆二十分钟最后发现是某一边的区间更新写错了。典型死循环场景是这样的你使用左闭右开区间[low, high)循环条件while (low high)mid 用向下取整计算。然后你在arr[mid] target和arr[mid] target的分支中把大于的情况写成了low mid而不是low mid 1。当区间只剩两个元素时比如 low 3, high 5mid 4如果arr[4] targetlow 被更新为 4区间变成[4, 5)和上一轮一模一样——low 没变、high 没变、mid 也没变于是死循环。为什么会出现这种错误因为你心里想的是arr[mid] 已经被比较过应该排除掉但写代码时却下意识地让 low 等于 mid 而不是 mid 1。这是心里想的逻辑和代码表达的逻辑不一致的典型例子。排查死循环有一个非常实用的套路在循环体里临时打印 low、high、mid 三个变量的值看它们是不是在某个状态上停滞不前。一旦发现 mid 的值反复出现且 low/high 不变就基本锁定是区间更新公式写错了。修复时记住一条检验规则每一次循环搜索区间必须严格缩小。如果某次循环后区间长度没有变小说明边界更新写错了。5.2 mid 计算溢出的历史教训另一个经典坑是 mid 的计算方式。很多人写mid (low high) / 2这个写法在 low high 不溢出的情况下没问题但一旦数组长度接近 int 上限的一半low high 就可能溢出变成负数导致 mid 为负数组越界访问程序直接崩溃。这看起来像是一个只有超大数据才会触发的问题但现实中并非不可能。很多语言里数组虽然理论上能开到接近 2^31但实际极少有人真去开一个十亿级别的 int 数组。不过这个坑真正阴险的地方在于你平时测试的小数据永远不会触发只有线上事故时才出现而且一出现就是崩溃级别。正确的写法是mid low (high - low) / 2。这个公式避免了直接相加用差值的一半再加回 low数学上等价但不会溢出。Java 标准库的二分查找早期版本就踩过(low high) / 2的坑后来才修复。我现在已经把永远用low (high - low) / 2写进了自己的代码规范里任何写二分的场合直接照抄不给自己犯错的机会。5.3 调试边界的实操套路用最小用例轰炸代码写二分查找的代码写完不等于完事必须立即用一组精心设计的测试用例验证边界逻辑。我自己的固定套路是这样的第一长度为 1 的数组。这是最容易暴露问题的用例因为此时 low 和 high 的关系非常敏感任何边界错误都会立刻显现。第二target 在数组首尾的情况。比如数组是[1, 3, 5, 7, 9]分别查找 1、9、以及比 1 小和比 9 大的值。这四个用例覆盖了最左侧最右侧完全小于完全大于四种极端情况。第三数组中存在重复元素的情况。用[2, 2, 2, 2, 2]测试 lower_bound 和 upper_bound确认返回的位置符合预期。第四数组长度为奇数、偶数、以及 0空数组。空数组虽然简单但很多实现会在 n 0 时直接数组越界值得专门测一下。这组用例跑完如果全部通过代码基本可以放心。如果不通过建议在关键位置加断言assert而不只是 print。断言的好处是能在错误发生的第一时间终止程序并给出信息print 则容易在大量输出中丢失关键信息。我曾经花过一个下午调试一个二分查找变体最后发现问题是数组本身没有严格排序有个元素被并发写坏了算法本身完全正常。这件事给我留下的教训是当算法怎么调都不对时先怀疑数据再怀疑代码。在工程排查中数据前置条件被破坏的概率往往比算法实现错误要高得多。6. 最后分享一点个人体会刚开始学顺序表查找时我觉得这东西太简单不值得花时间深究。后来在实际项目里被二分查找的边界条件、被缓存未命中的性能问题反复敲打之后才意识到计算机科学里真正难的不是那些看起来复杂的东西而是这些基础操作在真实硬件和真实数据环境下的行为。顺序查找和二分查找的每一个细节——哨兵怎么放、边界怎么收、mid 怎么算、什么时候用哪个——背后都对应着可以讲一整堂课的原理。如果你能把这篇里提到的坑都亲手踩一遍、再亲手解决一遍你的收获会远超背熟十个算法模板。基础的东西值得反复读、反复写、反复测试这是我这十几年来最真切的体会。