查找算法这个章节几乎每本数据结构教材都会把它放在排序后面、树和哈希之前看起来中规中矩但恰恰是这块内容最能区分“背过代码”和“真懂算法”两类人。我自己带过不少新人也面试过候选人发现二分查找的边界条件、线性查找的适用场景以及查找算法在不同数据结构上的权衡才是真正拉开差距的地方。这篇就借着“3.6 查找算法”这个章节把静态查找表里最核心的线性查找和二分查找从头到尾拆一遍包括原理、代码、边界坑、变体思路以及在工程项目里的选型经验。1. 查找算法解决什么问题先理解再动手1.1 查找算法在整章中的定位数据结构这门课里查找算法解决的核心问题只有一个给定一组数据和一个目标值快速判断目标值是否存在必要的时候把它的位置或相关信息取回来。听起来简单但这个“快”字背后藏着一整套复杂度权衡。教材把“查找算法”单独作为 3.6 节通常是在讲完线性表、数组、链表之后正式引入树和哈希之前这个位置很有深意——它是在用你已经掌握的线性结构去理解“怎么从数据里捞东西”这件事。很多初学者容易把查找和排序混在一起觉得先排序再查找或者先查找再排序顺序无所谓。实际工程里这两个操作是频繁交叉出现的索引文件要维护有序性才能快速定位数据库的 B 树叶子节点本身就是有序链表缓存系统要判断 key 是否存在才能决定是否回源。查找算法的本质是“一个动作多种策略”策略不同前置条件、时间开销、空间开销都不一样。这也是为什么教材强调“从静态查找表讲起”——静态意味着数据不频繁增删这时候可以把更多精力放在“怎么查得快”上而不用操心维护成本。1.2 三种主流查找方案的选型对比静态查找表里最经典的三条路线顺序查找、折半查找二分查找、以及按概率分配的分块查找索引顺序查找。教材里最常对比的就是前两个因为它们的思维模式完全不同顺序查找是“挨个看”二分查找是“猜中间根据大小缩小范围”。作为一个有实际开发经验的人我给新人的建议是先把这三者的适用场景焊死在脑子里查找方案前提条件时间复杂度空间复杂度适用场景顺序查找无O(n)O(1)无序小数据、链表结构、一次性查询二分查找有序 随机访问O(log n)O(1)迭代静态有序数组、频繁查询、数据量较大分块查找块间有序O(√n) ~ O(log n)O(块数)数据量大但需部分动态更新选择方案的第一原则不是“哪个快”而是“我的数据长什么样、能支持什么操作”。数组支持下标随机访问所以二分查找能直接拿到中位数链表只能从头部遍历就算数据有序二分查找每次取 mid 都要从头走一遍时间复杂度退化成 O(n log n)还不如老老实实顺序遍历。这就是为什么后面讲二分查找时我会反复强调“随机访问”这个前提——它不是一个抽象概念而是直接决定了算法能不能落地。2. 线性查找最笨的办法也有讲究2.1 线性查找原理与复杂度线性查找的思路一笔就能说完从第一个元素开始逐个和目标值比较相等就返回位置遍历完都没找到就返回失败。教科书上通常给这样的代码int sequentialSearch(int arr[], int n, int target) { for (int i 0; i n; i) { if (arr[i] target) { return i; } } return -1; }时间复杂度最好情况 O(1)第一个就是目标最坏情况 O(n)目标在最后或不存在平均情况 O(n / 2)。很多初学者觉得这个算法“太简单”不值得花时间。但实际上线性查找是最稳定的兜底方案尤其是面对链表这种不支持随机访问的结构。链表的查找只能从 head 开始 next无论你怎么优化都是 O(n)。有一个工程小优化值得说如果查找频率很高可以把“每次从头开始遍历”改成“记录上一次命中的位置下次从那个位置附近开始查”。这个技巧在局部性强的数据比如用户短时间内重复查看最近几条记录里能显著减少平均比较次数。虽然理论复杂度还是 O(n)但实际手感完全不同这种做法属于“常数级优化”在某些场景下能带来 30% 以上的吞吐提升。2.2 工程中的几个优化细节线性查找实现简单但细节处藏着不少有意思的点。第一个细节是哨兵位。教科书版本每次循环都要判断 i n 和 arr[i] target两个条件。如果先在数组末尾增加一个位置把 target 放在哨兵位arr[n] target然后从 0 开始遍历就不需要判断越界了找到的位置就是 target如果位置是 n 说明原数组里没有。代码改成int sequentialSearchSentinel(int arr[], int n, int target) { arr[n] target; // 前提是数组容量至少 n1 int i 0; while (arr[i] ! target) { i; } if (i n) { return -1; } return i; }这个技巧在数据量很大、查询次数很多时能减少约一半的比较操作数量少一个分支判断我自己在嵌入式环境里用过效果明显。但它有个代价必须保证数组末端有可用空间不能越界写入。工程里如果数组来自外部接口不满足这个前提这个优化就不能用否则会引入内存破坏的严重 bug。第二个细节是查找频率与数据排列。如果某些元素的访问概率明显高于其他元素可以把它们移到数组前端这是“自组织线性表”的思想。虽然静态查找表不允许随意改动顺序但在自己维护的缓存列表里这种“用过就往前挪”的策略非常实用典型例子就是 LRU 近似实现。第三个细节是不要忘了“查找失败”也是一种结果。有些应用场景里目标值不存在是常态比如黑名单校验此时线性查找必须完整遍历整个数据集。如果数据集是动态增长的可以考虑用布隆过滤器先做一次“大概率不存在”的判断滤掉绝大多数的无效查询再对可能存在的少量数据做精确线性查找。这是工程上非常经典的“粗筛 精查”组合。3. 二分查找核心原理与实现细节3.1 二分查找的适用前提有序与随机访问二分查找常被拿来当作“程序员基本功”的代表思路一句话能说清在有序序列中取中间值如果中间值等于目标直接返回如果目标小于中间值则在左半部分继续否则在右半部分继续直到区间为空。这个思路看起来无懈可击但落地时有两个前提经常被忽略。第一个是数据必须有序第二个是必须支持随机访问。数组满足这两个条件所以教材里的二分查找几乎都默认在数组上运行。有一个非常经典的坑对数组排序之后元素原来的位置信息就丢了。如果你需要返回的是“目标值在原数组中的下标”而不是排序后数组的下标就不能直接对原数组做二分。我见过不少人在实际开发里踩这个坑先把数组 sort 了一遍然后用二分查找找到位置之后发现下标对不上原始数据。解决方案一般是要么在排序前记录原始下标用结构体存 value 和 index要么不排序、直接采用其他查找方案。另一个前提是“单调性”。二分查找能够收敛依赖的是“如果 mid 大于 target那么 target 一定在左半边”这个确定性结论。这个结论只有在序列严格有序或至少非递减时才成立如果数据是乱序的mid 的位置信息毫无意义。有些人拿无序数组直接二分运气好可能撞上但本质上是在瞎猜正确率毫无保证。3.2 边界与 mid 计算的细节这些是坑二分查找的边界条件是整个章节里最容易写错的点。这里我把几种常见写法统一整理一遍包括它们的初始条件、循环条件和收缩方式。第一种写法左闭右闭区间 [left, right]int binarySearch(int arr[], int n, int target) { int left 0, right n - 1; while (left right) { int mid left (right - left) / 2; if (arr[mid] target) { return mid; } else if (arr[mid] target) { left mid 1; } else { right mid - 1; } } return -1; }这种写法里right 初始化为 n - 1循环条件是 left right收缩边界时 left mid 1 或 right mid - 1。核心逻辑是mid 被检查之后无论结果如何它都不应该再出现在下一次搜索区间里所以要加减 1。第二种写法左闭右开区间 [left, right)int binarySearch(int arr[], int n, int target) { int left 0, right n; while (left right) { int mid left (right - left) / 2; if (arr[mid] target) { return mid; } else if (arr[mid] target) { left mid 1; } else { right mid; } } return -1; }这种写法里right 初始化为 n循环条件是 left right右边界收缩时 right mid因为 right 本身是不在区间内的mid 作为当前位置被排除后可以直接把右边界挪到 mid。两种写法的差别只在边界代表的语义上一个闭一个开代码逻辑会跟着变。还有一个高频面试点为什么 mid 不直接写成 (left right) / 2因为当 left 和 right 都是很大的 int 时两者之和可能溢出 int 范围。用 left (right - left) / 2 虽然多一步计算但安全性高得多。这个细节在算法竞赛和工程代码里都有实际意义我在早期写代码时也输出过负数索引排查半天才发现是加法溢出了。3.3 迭代实现与递归实现怎么选二分查找既可以迭代实现也可以递归实现。从工程角度看我更推荐迭代原因有三点。第一迭代版没有额外栈空间空间复杂度 O(1)递归版虽然深度只有 O(log n)但每一次递归调用都有函数栈开销。在嵌入式、高性能服务这类对资源敏感的环境里迭代版会更稳妥。第二迭代版不容易写出栈溢出。虽然二分查找的递归深度只有 log n 级别不会真的把栈写爆但如果后续把这个思路扩展到更复杂的场景比如递归深度不可控的树形二分就可能出问题。养成迭代优先的习惯长期来看更安全。第三迭代版调试更直观。你可以直接打印 left、right、mid 三个值一步步跟踪区间收缩过程递归版则要把中间状态一层层传上去脑内推演的成本更高。递归版也不是没有价值。它的代码更简洁语义更接近数学定义适合用来讲解算法思想。我一般会在教新人时先给递归版本帮助理解再让他们改成迭代版本加深记忆最后在生产代码里统一用迭代版。int binarySearchRecursive(int arr[], int left, int right, int target) { if (left right) { return -1; } int mid left (right - left) / 2; if (arr[mid] target) { return mid; } else if (arr[mid] target) { return binarySearchRecursive(arr, mid 1, right, target); } else { return binarySearchRecursive(arr, left, mid - 1, target); } }这个递归版配合左闭右闭区间的写法语义很清晰区间为空说明没找到返回 -1否则继续缩小区间。理解了这一版再看各种变体就顺了。4. 二分查找的变体真正面试和工作中常用的形态4.1 找左边界和右边界教材基础的二分查找只解决一个问题数组里存不存在 target存在就返回下标。但实际需求往往更复杂。比如有序数组里有很多重复元素我想知道 target 第一次出现的位置或者我想知道 target 最后一次出现的位置或者我想找第一个大于 target 的元素位置。这些需求在工程里都很常见比如统计某个分数的排名、按时间戳定位日志区间。以寻找左边界为目标核心思路是当 arr[mid] target 时不直接返回而是收紧右边界继续在左半边搜索直到循环退出此时 left 指向的位置就是第一个等于 target 的元素。代码如下int lowerBound(int arr[], int n, int target) { int left 0, right n; while (left right) { int mid left (right - left) / 2; if (arr[mid] target) { left mid 1; } else { right mid; } } return left; // 返回第一个 target 的位置 }这个函数其实做的是 C 标准库里的 lower_bound返回“第一个不小于 target 的元素下标”。如果所有元素都小于 target返回 n如果没有元素等于 target返回的是应该插入的位置。同理upper_bound 返回“第一个大于 target 的元素下标”实现只需要把 arr[mid] target 改成 arr[mid] target 即可。有了 lower_bound 和 upper_bound重复元素的查找问题就解决了第一个等于 target 的位置是 lower_bound 返回的下标需要再校验值是否等于 target最后一个等于 target 的位置是 upper_bound 返回的下标减 1。这两个函数是工程中极其常用的一组工具在 Java 里有 Arrays.binarySearch 可以近似替代在 C 里直接调 std::lower_bound在 Python 里可以用 bisect 模块。4.2 浮点数二分换个场景同样适用二分查找不仅能用在整数数组上也能用在连续实数范围内。“浮点数二分”最常见的应用是解方程或求函数极值。核心思想是如果函数 f(x) 在区间 [l, r] 上单调那么“f(mid) 和目标值比较”这个逻辑依然成立只是区间收缩不再依赖下标而是依赖左右端点。一个典型例子求 sqrt(2) 的近似值。问题是“找到 x使得 x * x 2”函数 x^2 在正数范围内单调递增所以可以二分逼近double sqrtBinary(double target) { double left 0, right target; for (int i 0; i 200; i) { // 固定迭代次数控制精度 double mid (left right) / 2; if (mid * mid target) { left mid; } else { right mid; } } return left; }这里用固定迭代次数代替 while (right - left eps)好处是避免浮点精度导致死循环。200 次迭代对于 double 来说已经足够收敛到机器精度极限再多的迭代没有意义。浮点数二分在图形学、物理引擎、数值计算里有广泛应用理解它有助于把“二分思想”从数组扩展到连续空间。整数的 [left, right] 和浮点数的 [left, right] 有一个关键差异整数区间靠下标移动每次必然缩小浮点区间靠端点收缩如果不设迭代次数上限或者 eps 设得过小可能陷入无限循环。我在实际调试时经常把 eps 设成 1e-9结果发现某些边界值附近算法一直跳不出来后来统一改成“固定迭代 100~200 次”问题直接消失。4.3 二分思想在其他数据结构的延伸二分思想不局限于数组。跳表Skip List本质上就是在链表上做多层二分查找每一层跨越更多节点搜索时从高层开始逐层下降平均时间复杂度 O(log n)。Redis 的有序集合ZSet底层就用了跳表结构。理解了数组二分查找再去看跳表会很容易它用“空间换时间”弥补了链表不支持随机访问的缺陷。二叉搜索树BST也可以理解为一种动态的二分查找结构每个节点像二分查找里的 mid左子树对应左半区间右子树对应右半区间。它的优势是插入删除也是 O(log n)但劣势是如果插入顺序不好会退化成链表所以才有 AVL 树、红黑树这些自平衡变体。这些内容虽然不在“3.6 查找算法”这一节里但思维一脉相承。另外一个经常被忽略的延伸是三分查找。对于单峰函数可以先比较两个三等分点根据函数值走势决定舍去哪一段时间复杂度 O(log n) 但常数比二分大。不过工程上用三分查找的场景相对比较少一般遇到峰值问题直接上梯度类方法或枚举精度更高这里就不展开了。5. 常见问题与排查技巧实录5.1 死循环是怎么产生的二分查找最常见的 bug 就是死循环。以左闭右闭写法为例如果收缩边界时写成 left mid 而不是 left mid 1在区间长度为 2 时就会卡死。比如 left 5, right 6mid 5如果 arr[5] targetleft 被更新为 5区间没有缩小下次循环还是 5 和 6无限重复。排查死循环的标准手法是打印每次循环的 left、right、mid 三个值。如果发现 left 和 right 在某一轮之后不再变化就说明收缩策略有问题。还有一个更系统化的检查方法人为构造“区间长度 1”和“区间长度 2”两种极端情况手动跑一遍代码看边界是否按预期收缩。# 假设打印输出 left0, right1, mid0 left0, right1, mid0 # 到这里发现 left 没有变化死循环如果是左闭右开写法死循环的常见诱因是把 right mid 误写成 right mid - 1。因为右开区间的 right 不在搜索范围内直接减 1 会把可能存在的目标位置跳过去但与此同时区间又可能变大逻辑就乱了。建议写代码时把区间语义注释出来提醒自己 left 包含、right 排除或不排除。5.2 重复元素导致的结果不稳定基础版二分查找遇到重复元素时返回的下标是不确定的——它可能命中任何一个等于 target 的位置取决于 mid 怎么计算。这在某些场景下没问题但如果你需要“第一个位置”或“最后一个位置”就必须用 4.1 节的 lower_bound / upper_bound 思路。曾经有个需求日志文件按时间戳排序要统计某分钟内有多少条日志。我一开始用基础二分查找找到任意一条命中记录然后向前向后扩展统计结果发现当这一分钟内日志量极大时扩展步骤无限接近 O(n)性能崩了。后来改成用 lower_bound 定位起始位置、upper_bound 定位结束位置两个下标一减就是总数时间复杂度稳定在 O(log n)。这个案例让我印象很深基础二分查找到变体二分查找不是“炫技”而是解决真实性能问题的必要手段。另一个相关的坑是数组中存在多个等于 target 的元素时如果只需要判断存在性直接返回 true 即可但一旦要处理“索引范围”必须用边界变体不能依赖基础版的返回值。5.3 从无序数据中“硬做二分”会怎样有人会问数据本身无序但能不能先排序再二分可以但时间复杂度变成了 O(n log n)排序 O(log n)查找如果只查一次还不如线性查找 O(n) 来得快。而且如果数组元素带原始位置信息排序会导致下标错乱后面还得额外维护映射关系。更关键的是无序数据集合往往来自动态场景比如用户实时提交的内容无法保证查询前数据是静止的。这种情况下排序的代价无法摊销二分查找的“有序”前提本身就不成立。正确做法是如果查询次数很少用线性查找兜底如果查询次数多且数据会变动考虑用哈希表把查找复杂度降到 O(1) 平均只有当数据量大、查询频繁且几乎不变时才值得做一次完整排序然后用二分查找。我在一个配置管理模块里遇到过类似问题配置项几千条每次都全量加载到内存但查询很频繁。最初我用线性查找接口平均耗时几十毫秒压力测试时直接飙升到秒级。后来把所有配置项按 key 排序后放入数组用二分查找平均耗时降到微秒级内存没有额外开销。这个经历说明算法选型要结合实际的查改比查多改少排序值得查少改多哈希或线性更合适。6. 查找算法在真实项目中的应用与心得6.1 有序数组不等于永远用二分数据量和访问成本数据有序只是二分查找的必要条件不是充分条件。决策时还要看数据量级和单次比较的代价。如果数组只有几十个元素二分查找和线性查找的差异微乎其微但代码复杂度明显更高。新人阶段容易陷入“算法越高级越好”的误区真到工程里重要的是可读性和可维护性。我见过有人在一个长度不超过 20 的常量数组上用二分查找理由是“这样显得专业”结果后来维护的人反复确认边界条件白白浪费了大量时间。反过来如果数组很大几百万甚至上亿二分查找的 log n 优势就非常明显。 n 1,000,000 时线性平均需要 50 万次比较二分最多 20 次比较差距是几个数量级。这种情况下数据的存储结构也要考虑如果用链表存储二分根本跑不起来必须换数组或跳表。单次比较代价也很重要。如果数组元素是简单的 int比较很快如果是长字符串或复杂对象每次比较都要调用回调函数一次查找可能要执行十几次字符串比较。此时可以考虑在构建索引时把比较 key 提取出来比如把字符串转成哈希值后排序或者用 Trie 树这类更高效的字符串查找结构。6.2 一种更容易维护的写法开区间还是闭区间很多团队代码风格不统一有人用闭区间有人用开区间代码 review 时经常因为边界条件吵起来。我的建议是在一个团队或一个项目里统一一种风格并且在函数注释里写清楚“left 和 right 分别代表什么”。就我自己的偏好而言左闭右开 [left, right) 在配合 lower_bound / upper_bound 时更顺手。原因是这类边界查找的返回值和区间语义天然对齐lower_bound 返回的 left 是第一个满足条件的位置如果没找到正好返回区间右端点 n语义就是“目标应该插入的位置”。这种一致性让调用方不容易犯错。闭区间 [left, right] 的优点是循环条件直观left right适合初学阶段理解基本思想。但到了写变体时闭区间需要额外处理“mid 已检查必须排除”的逻辑容易在重复元素场景出错。如果你是刚接触这块内容我建议先把闭区间写好再花半小时改成开区间自己对比两套代码的差别以后看到任何一种写法都不慌。6.3 一个小技巧把查找函数写成模板或高阶函数工程上查找算法很少只针对 int 数组。真实需求可能是按用户 ID 查用户对象、按文件名查文件信息、按订单号查订单记录。这时候给每种类型各写一个二分查找函数是非常蠢的做法维护成本极高。C 工程里可以用模板 比较器Java 里可以写泛型 ComparatorPython 里直接传 key 函数核心都是“把比较逻辑和查找逻辑解耦”。这里给一个 Java 风格的例子思路是通用的public static T int binarySearch(List? extends T list, T target, Comparator? super T comparator) { int low 0, high list.size() - 1; while (low high) { int mid low (high - low) / 2; int cmp comparator.compare(list.get(mid), target); if (cmp 0) { low mid 1; } else if (cmp 0) { high mid - 1; } else { return mid; } } return -(low 1); // 返回插入点 }同一个函数可以用于 int 比较、字符串比较、甚至自定义对象比较。实际开发中Java 的 Collections.binarySearch、C 的 std::binary_search / std::lower_bound 已经封装好了这些能力优先用标准库不要重复造轮子。只有在标准库满足不了特殊需求比如要在二维数组上做按行二分、或者在多个有序数组上做联合查找时再基于上面的模板自己扩展。我做项目时习惯把查找、排序这类基础操作统一封装成一个“AlgorithmUtils”工具类所有业务代码都走它。这样一旦底层实现需要优化比如从二分改成更高效的插值查找或者换成并行查找只改一处所有调用方都受益。这个习惯帮我省了非常多后期重构的麻烦。查找算法这一节的代码量不大但思维密度很高。它教会我的不是“会写二分”这个动作而是“如何在约束条件下选择最优的检索策略”这个思维模型。数组有序且静态二分是王者数据无序且量小线性已经够用数据频繁变动哈希或者平衡树更合适。把这套权衡逻辑吃透后面学树、学哈希、学索引都会觉得顺理成章。我强烈建议你把书上的示例代码亲手敲一遍然后改改边界条件、换换重复元素亲眼看看结果会怎么变。这个章节值得多花点时间。