折半查找算法详解：原理推导、代码实现与六大变种题型一步到位

折半查找这东西几乎是每个学编程的人都会撞上的经典题型。校招笔试、考研专业课、面试手撕代码翻来覆去就是它。我见过不少候选人原理讲得头头是道一到手写代码就暴露出各种边界问题要么死循环要么越界要么查找结果不对。今天就把这个题目彻底掰开揉碎从原理推导、代码实现到各种变种题型一步到位讲清楚。我会把折半查找法涉及的核心知识点、常见题型和坑点全部过一遍配合可以直接抄的代码模板。无论你是正在准备考试的学生还是面试前临时抱佛脚的求职者这篇文章都能让你在最短时间内把这块短板补上。1. 折半查找法的核心思想与适用前提1.1 一句话理解折半查找折半查找Binary Search的逻辑其实特别朴素就是不断把查找范围一分为二然后判断目标值在左半边还是右半边哪边有可能就去哪边继续找。整个过程有点类似于我们日常玩猜数字游戏告诉你一个1到100之间的数每次猜完只告诉你猜大了还是猜小了最聪明的策略就是每次都猜中间值。第一次猜50如果大了就猜25如果小了就猜75这样每次都排除掉一半的选项最多猜7次就能锁定结果。折半查找就是这个思路的标准算法化版本。这个每次砍半的思路直接带来了对数级别的时间复杂度。也就是说就算数据量从1000涨到100万查找次数的增长也只是从10次涨到20次这个效率优势在数据规模越大的时候越明显。1.2 两个硬性前提缺一不可第一个前提是数据必须有序。折半查找在每次比较后需要根据中间值和目标值的大小关系来决定丢弃哪一半如果数据本身就是无序的这种丢弃一半的判断就不成立。比如数组是[5, 3, 8, 1, 9]你比较了中间值8之后判断目标值应该在左半边但实际上目标值可能就夹在右边那堆无序数据里这必然导致查找结果错误。第二个前提是数据必须支持随机访问。也就是能在O(1)时间内直接拿到任意下标对应的元素。数组完美满足这一点但链表不行因为链表访问中间节点需要从头遍历到中间位置光是找中间值就得花O(n)的时间整个算法的复杂度优势就荡然无存了。所以如果看到题目给出的是有序链表不要直接套折半查找而是应该考虑跳表这类专门的数据结构。注意实际项目中如果数据是无序的又想用折半查找得先做一次排序。排序的时间复杂度最低是O(n log n)所以这种情况下要先权衡一下如果查找次数很少直接线性扫描可能更划算如果查找非常频繁那排序一次后面的查询就都受益了。2. 判定树、时间复杂度与平均查找长度推导2.1 从搜索过程画出判定树对于理解折半查找的复杂度判定树是一个非常直观的工具。假设有一个长度为11的有序数组下标从0到10。第一次折半查找中间位置是(010)/25我们拿下标为5的元素和目标值比较。如果目标值较小下一步的查找范围是0到4中间位置是(04)/22如果目标值较大下一步的查找范围是6到10中间位置是(610)/28。按照这个规律继续画下去可以发现整个查找过程其实是在一棵二叉树上做路径搜索。树根是下标5左子树的根是下标2右子树的根是下标8每一层对应一次比较。查找成功的次数就等于目标节点在这棵树里的深度加1。这个视角在笔试中很重要因为很多题目会直接问查找某个元素需要比较几次本质就是让你在这棵判定树上模拟路径。2.2 时间复杂度为什么是O(log n)每次比较都会将待查找区间缩小为原来的一半。假设初始区间长度为n经过k次比较后区间长度变为n/2^k。当这个长度缩到1的时候就能确定答案了。所以理论上最多需要的比较次数满足n/2^k 1也就是k log₂(n)。我见过很多初学者把时间复杂度写成O(n/2)这个错误在于只看到第一次比较排除了一半就认为复杂度是O(n/2)忽略了每一轮都在持续减半这个事实。真实的情况是经过k轮后长度为n/2^k这是个指数衰减的过程。所以折半查找的时间复杂度是O(log n)而不是O(n/2)这两者有本质区别。2.3 关键公式平均查找长度ASL考试和面试中另一个高频考点是平均查找长度。对于长度为n的有序表折半查找在查找成功时的平均比较次数约等于log₂(n1)-1。这个公式看起来有点突兀但它其实可以直接从判定树推导出来。一棵深度为h的满二叉树的节点总数是2^h-1反过来如果树里有n个节点深度约等于log₂(n1)。而每个节点的平均查找次数是这一层节点的比较次数对于比较均衡的判定树来说平均查找长度收敛于log₂(n1)-1。举个例子n100时log₂(101)约等于6.66减1就是5.66也就是平均比较大约6次就能找到目标元素。最坏情况下则是树的深度约等于⌊log₂n⌋1次。这个公式用不着死记硬背理解了判定树的结构考试现场花30秒就能推出来。3. 核心代码实现与边界条件详解3.1 标准的迭代实现折半查找的实现本身不复杂但代码里的边界条件极其容易出错。这是最常见的教科书写法我直接给出完整代码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; }这段代码有三个地方值得专门讲解。第一个是while (left right)而不是left right。原因在于当left right的时候区间里还剩下一个元素这个元素可能是目标值必须再比较一次。如果用left right循环会提前终止导致漏掉这个元素。我第一次写这个代码时就在这个问题上栽过跟头原本以为只剩一个元素肯定已经在之前检查过了但实际上不是每个元素都有机会被当作mid检查到。第二个是mid left (right - left) / 2而不是mid (left right) / 2。两者的计算结果在数学上是等价的但直接相加left right可能会在left和right都很大时发生整数溢出。比如left和right都接近 2^31 - 1加起来超过 int 类型的最大值结果变成负数程序直接出错。用left (right - left) / 2就完全规避了这个问题。这是一个在面试中体现代码素养的细节。第三个是更新边界的时候left mid 1和right mid - 1必须带上加减1。因为arr[mid]已经和 target 比较过了确定不等于 target所以下一轮查找区间必须排除掉 mid。如果写成left mid或者right mid当查找区间长度为2的时候mid会和left或right相等更新后区间没有缩小就会陷入死循环。提示面试时写完代码强烈建议自己手动模拟一个长度为2或3的小数组把每一步的 left、right、mid 走一遍。大部分边界 bug 在这种手动模拟中都能暴露出来。3.2 递归实现的写法与注意点递归版本的思路和迭代完全一致只是形式上不同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); } }递归的终止条件是left right这和迭代版本中while (left right)是镜像关系。很多人在写递归版本时容易把终止条件写成left right这同样会漏掉单个元素的判断。递归版本的好处是逻辑更清晰和判定树的天然结构对应缺点是每递归一层都会产生函数调用栈的开销并且如果输入的数组很大、递归深度很深理论上存在栈溢出风险。对于折半查找来说递归深度是 O(log n)n 在普通范围内比如 10 亿深度也只有 30 层左右所以栈空间通常不会有问题。但工程上如果追求极致性能还是用迭代版本更稳妥。3.3 边界情况的处理目标值不存在、重复元素、空数组目标值不存在时标准实现返回 -1这个逻辑很简单。但如果题目要求返回目标值应该插入的位置那就需要稍微变通一下。在目标值不存在的情况下循环结束时left指向的就是第一个大于目标值的位置也就是插入位置。这个性质在后面讲变种题型时会高频用到。重复元素是折半查找的另一个经典考点。标准的折半查找只保证返回某一个等于目标值的下标但不保证是第一个或最后一个。例如arr [1, 2, 3, 3, 3, 4, 5]目标是3标准折半查找可能在第一次遇到下标2的3时就返回了也可能通过某种顺序走到下标4的3。如果题目要求返回第一个3或最后一个3就需要在找到目标值之后继续向一侧收缩区间具体方法在下一章详细说。空数组是最容易被忽视的极端情况。无论是迭代还是递归如果n 0或者left right都应该直接返回 -1不需要做任何额外判断。这个情况在代码里天然被处理了但如果你用的是别的方式初始化right比如right n而不是right n - 1那空数组时就会出错。所以我建议所有从头写折半查找的人都以left 0; right n - 1为默认起始状态这是最不容易出错的形式。4. 你必须掌握的六大变种题型在实际考试和面试中直接考标准折半查找的题目反而少更多是考它的变体。这些变体本质上都是在标准二分框架内做细微调整。我把最高频的六种整理出来每一种都给出代码模板和关键思路。4.1 查找第一个等于目标值的位置左边界这题的要求是数组中有多个重复元素返回最左边的那个。核心思路是即使在arr[mid] target时也不急着返回而是把right收缩到mid - 1继续在左半边找直到区间耗尽。int findFirst(int arr[], int n, int target) { int left 0, right n - 1; int result -1; while (left right) { int mid left (right - left) / 2; if (arr[mid] target) { right mid - 1; if (arr[mid] target) { result mid; } } else { left mid 1; } } return result; }这个写法的关键变化是arr[mid] target时记录result mid然后继续向左收缩。注意arr[mid] target和arr[mid] target的处理合并成了一个分支因为两者都需要往左走。当你习惯了这种写法即使题目改成查找第一个不小于目标值的位置也只是把判断去掉而已。4.2 查找最后一个等于目标值的位置右边界和左边界镜像对称找到目标值后往右收缩int findLast(int arr[], int n, int target) { int left 0, right n - 1; int result -1; while (left right) { int mid left (right - left) / 2; if (arr[mid] target) { left mid 1; if (arr[mid] target) { result mid; } } else { right mid - 1; } } return result; }只要理解了左边界的逻辑右边界就是反过来arr[mid] target时向右收缩并记录结果。4.3 查找目标值的插入位置LeetCode 的第 35 题就是这道题。要求给定一个有序数组和目标值如果找到就返回下标如果没找到就返回它应该插入的位置。这个题完全不需要额外记录循环结束后left就是答案。int searchInsert(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 left; }为什么left一定是插入位置这需要理解循环不变式在整个查找过程中arr[left - 1]始终小于 target或不存在arr[right 1]始终大于 target或不存在。循环退出时left right 1所以left左侧都小于 targetleft位置恰好是第一个大于等于 target 的元素这就是插入位置。4.4 在有序数组中用二分法求平方根LeetCode 第 69 题求非负整数 x 的平方根只返回整数部分。这个题的精髓在于二分答案——不是二分数组下标而是二分值域。int mySqrt(int x) { int left 0, right x; int ans -1; while (left right) { int mid left (right - left) / 2; if ((long long)mid * mid x) { ans mid; left mid 1; } else { right mid - 1; } } return ans; }这里的mid * mid我专门做了强制类型转换避免 int 溢出。比如 x 2147483647mid 取到 46341 时mid * mid 已经超出 int 范围了如果不提升成 long long 就溢出了。这个细节在数值型二分的题目中特别重要也是一个很容易被忽略的坑。这类题的本质是把判断某个值是否满足条件抽象成一个单调函数然后对这个函数的定义域做二分。4.5 153. 旋转有序数组的最小值经典题目一个原本递增的有序数组在某个未知位置进行了旋转比如 [0,1,2,4,5,6,7] 变成 [4,5,6,7,0,1,2]要求找出最小值。这题同样可以用二分。int findMin(int arr[], int n) { int left 0, right n - 1; while (left right) { int mid left (right - left) / 2; if (arr[mid] arr[right]) { left mid 1; } else { right mid; } } return arr[left]; }这里的判断依据是如果arr[mid] arr[right]说明最小值在 mid 的右侧否则最小值在 mid 位置或左侧。这个题和标准二分的一个显著区别在于循环条件变成了left right而不是left right并且right mid时没有减 1。因为这里要找的是一个最小值点mid 自身有可能是答案所以不能直接排除。这里需要小心中间值的选取。如果mid偏向左侧left (right - left)/2配合left right的循环条件最终一定能收敛。4.6 二分答案类型的通用模板有一类题不直接对一个数组做二分而是二分答案本身。比如给定一个数组每次操作可以让某些元素减少问最少多少次操作能让最大值不超过K这类问题的特征是答案的范围是固定的整数区间并且存在一个单调的判断函数 f(mid)可以判断答案是 mid 时是否可行。int check(int mid, ...) { // 根据题目要求实现返回 mid 是否可行 } int main() { int left 0, right 1e9; while (left right) { int mid left (right - left) / 2; if (check(mid, ...)) { right mid - 1; // 尝试更小的答案 } else { left mid 1; } } return left; }这类题目在竞赛和面试中都很常见本质就是通过二分把求解问题转化为判定问题。只要能写出单调的 check 函数就可以用这套模板套进去。5. 实际工程场景中的折半查找应用很多人以为折半查找只在考试中出现其实它在真实工程项目里的覆盖面非常广。理解这些场景不仅能帮你回答面试中的这个算法有什么实际应用这类问题也能让你在真实的系统设计中有更多工具可选。5.1 有序数组与数据库索引数据库的 B 树索引本质上可以理解为一种多路折半查找的变体。B 树每个节点包含多个键值在节点内部查找时用的就是折半查找。比如 MySQL 的 InnoDB 引擎索引页内部会对有序的主键值做二分查找来精确定位记录的位置。在代码层面如果你维护的是一份常驻内存的有序数组比如配置表、路由表用折半查找替代线性扫描通常能带来几百倍的性能提升。我之前优化过一个路由匹配模块原来用 for 循环逐个匹配几百条路由规则QPS 上不去改成折半查找后延迟立刻降了一个数量级。5.2 监控系统里的指标定位在监控系统中时序数据通常是按时间戳排序存储的。要根据时间范围查询某段时间的指标最快的方式就是先用折半查找找到起始时间戳再线性向后扫描一小部分。因为监控数据可能一天有几百万条用线性扫描从头开始找起始位置代价非常高折半查找直接把这一步变成了 O(log n)。这一类场景的技术要点是虽然时间戳严格递增时才能用二分但实际数据往往存在重复时间戳所以一般配合前文讲的左边界查找变种来定位第一个满足条件的时间戳。5.3 单调函数求根与数值计算在数值计算、图形学、游戏开发领域经常需要求解一个单调函数的零点或满足某条件的边界值。比如给定一个距离函数求某个值对应的参数或者在二分查找的框架下用浮点数逼近方程的根。这类问题不需要严格的数组有序只要函数单调就天然满足折半查找的前提。工程里的浮点数二分需要注意一点判断条件是right - left eps而不是left right否则由于浮点数精度问题会死循环。6. 常见错误与排错技巧大全折半查找代码看似简单实际写起来踩坑的人不在少数。我把这些年见过的、自己踩过的高频问题整理成一个速查表供你对照排查。常见错误现象原因与解法while (left right)漏查最后一个元素当 left right 时区间还有一个元素需要继续比较改成mid (left right) / 2大数据量时数组越界或结果异常left right 可能溢出改成left (right - left) / 2left mid或right mid死循环mid 已经被比较过应该从区间中排除用mid 1或mid - 1没有处理空数组运行时崩溃在入口处判断 n 是否为 0数组中存在重复元素但按标准二分写返回的不是题目要求的边界位置需要改成左/右边界查找变种二分答案时 mid * mid 溢出结果异常用 long long 接收乘法结果或改用除法/牛顿迭代法浮点数二分没有设置精度 eps死循环用while (right - left eps)代替等值判断目标值不存在时直接返回 -1与题意不符确认题目要求返回插入位置还是 -1不要习惯性写 -1除了表格里的问题还有两个调试技巧经常帮我快速定位错误。一个是打印日志在 while 循环里把 left、right、mid 都打出来代码跑一遍基本就能看出区间缩小的趋势是否正常。另一个是用一个长度为 2 或 3 的小数组手动模拟如果你手算的每一步结果和代码打印的一致那大概率逻辑就是对的如果第一步就分叉了说明判断分支写反了。提示面试时如果时间紧张可以在写完代码后主动提一句我验证一下边界情况然后手动模拟空数组、单元素数组、目标值在开头、目标值在末尾这四种情况。这个动作本身就能给面试官留下好印象因为它说明你具备工程上的严谨性。最后再分享一个我个人在实际做题中的体会折半查找这类基础算法靠看别人的代码是记不牢的一定要自己动手敲一遍然后用几组刁钻的测试数据跑一遍。把左边界、右边界、插入位置、旋转数组这几个变种各写一遍写完后自然会形成肌肉记忆。以后遇到任何有序查找的题目第一时间就会想到折半查找而不是线性遍历。这个思路一旦形成你解题的效率会有非常明显的提升。