不需要额外前置说明直接输出博文。我注意到内容长度要求很严格下面的内容会尽量丰富扎实。1. 为什么要用二分查找一个被低估的基础算法如果你刷过题、做过在线测评或者平时写业务代码需要在一个已经排好序的数组里找某个数二分查找这个名字肯定不陌生。它几乎是最早进入教科书的那批算法之一但说实话真正能一次写对的人并不多。我见过不少人把循环条件写成left right结果目标值不在数组里时直接死循环也见过不少人算中间位置直接(left right) / 2数组一大就溢出崩溃。这个标题叫“二分查找(在排序数组查找元素)(2)”后面带了个“(2)”大概率是系列文章或练习的第二篇。第一篇通常讲基础概念第二篇就要开始抠细节了。这篇文章我打算从几个维度展开二分查找能解决什么问题、为什么它必须要求排序数组、手写基础版和进阶版的完整代码、在PTA这类在线测评里怎么应对函数题、以及我这些年踩过的坑和排查思路。先回答一个最常见的问题二分查找到底解决什么问题一句话它解决的是“在有序序列中快速定位目标”的问题。线性查找要从头扫到尾数据量是 n 时最坏要比较 n 次二分查找每次比较后可以排除掉一半数据最多只需要比较 ⌊log₂n⌋ 1 次左右。n 等于 100 万时线性查找可能跑几十万次二分查找大概只需要 20 次比较。这种差距在数据量大的时候会非常明显尤其是当“比较”本身很昂贵时比如数据库里按索引查记录、二分搜索树查找、有序数组的区间统计等。适合学这篇文章的人我分成三类第一类是刚学完C语言或Python基础准备把算法题练起来的学生第二类是正在准备笔试面试、需要把二分查找的各种变体搞清楚的人第三类是工作中偶尔要处理有序数据、但不想每次都被边界条件折磨的开发者。后面内容不会停留在“背模板”层面我会把每个关键判断背后的原理讲清楚这样你遇到题目变体时才知道该怎么调整。2. 二分查找核心思路为什么说它是一台“猜数字机器”2.1 从猜数字游戏理解二分二分查找的思维模型其实特别生活化。想象一个游戏裁判心里想了一个 1 到 100 之间的整数你每猜一次裁判会告诉你“大了”还是“小了”目标是用最少的次数猜中。最笨的办法是从 1 开始一个一个试运气好一次猜中运气不好得猜 100 次。聪明的办法是每次都猜当前范围的中间值第一次猜 50如果裁判说“大了”目标就落在 1 到 49第二次猜 25如果“小了”目标就落在 26 到 49这样每次把区间砍掉一半最多 7 次就能猜中。这个游戏就是二分查找的完全写照。数组的查找过程其实就是不停地在问“目标值比中间位置的值大还是小”根据回答决定去左半边还是右半边继续找。中间值就是“猜测值”数组的区间就是“猜测范围”。理解了这个游戏你就理解了二分查找的全部逻辑基础。2.2 排序数组这个前提为什么不可动摇二分查找的核心操作是“比较中间值和目标值然后扔掉一半”。它之所以能放心扔掉另一半靠的是一个数学上的强前提数组必须有序。假设数组是 [3, 1, 2, 5, 4]你拿中间值 2 去和目标值 5 比较发现目标值更大你能断定 2 右边一定有 5 吗不能因为数组无序5 可能在任何位置。但如果是 [1, 2, 3, 4, 5]中间值是 3目标值 5 更大那么 5 一定在右半边可以放心把左半边丢掉。这就是排序数组的意义它给了你一个“区间淘汰”的合法性。你不需要看完整个数组只需要知道某个边界上的值比目标值大或小就能把另一侧的所有元素排除。这也是二分查找和“分块查找”“哈希查找”最大的区别——二分完全依赖有序性不要求额外空间却牺牲了还没排序时的直接查找能力。实际工程中这意味着两件事。第一如果你要在无序数组里反复查找应该先排序但排序本身有 O(n log n) 开销只有在查找次数足够多时才划算。第二如果数据是动态插入的维护一个有序数组的成本可能很高插入 O(n)这种场景更适合用平衡二叉树或跳表而不是硬套二分查找。2.3 区间不变量写对二分的第一性原理很多人写二分查找会写错甚至写出来了也不知道自己为什么对。我强烈建议所有人在写二分之前先想清楚一个问题你维护的区间[left, right]到底表示什么这个“区间表示什么”在算法领域叫循环不变量loop invariant。循环不变量是在循环开始前为真、每次迭代后仍然保持为真的条件。只要你保证了不变量在循环中不被破坏循环结束时就能得到正确结果。二分查找最常见的两种不变量定义是左闭右闭区间[left, right]表示目标值可能存在的范围包含 left 和 right。左闭右开区间[left, right)表示目标值可能存在的范围包含 left不包含 right。这两种定义会直接改变你的循环条件、边界更新方式和初始值。很多人就死在混用上循环用left right更新却用right mid - 1结果该跳过的没跳过不该跳过的被跳过了。我建议初学者先把“左闭右闭”这一定义焊死在脑子里因为它的逻辑最直观。每轮循环开始前你都告诉自己目标值如果存在一定在[left, right]这个闭区间里。那么循环条件当然是left right因为当 left 和 right 相等时区间里还有一个元素没检查。mid 被检查后如果目标值在左侧就更新right mid - 1如果在右侧就更新left mid 1。这样更新后新区间仍然满足“目标值可能存在于此区间”这一不变量。如果你选了“左闭右开”循环条件就成了left right因为 left right 时区间已经空了。更新边界时右侧是开区间所以左边更新为left mid 1右边更新为right mid直接把右开边界移到中间位置。这套逻辑也能跑得很好STL 里的lower_bound和upper_bound就基于类似思想。关键点不在于哪种定义“更对”而在于你写完整个代码后循环条件、mid 更新、边界移动三处必须和同一种定义自洽。这是二分查找里最容易出错、也最值得花时间想清楚的地方。3. 手写二分查找基础版到进阶版的完整代码解析3.1 基础版在排序数组中查找指定元素先说最标准的版本。给定一个升序排列的整型数组nums和一个目标值target如果target存在则返回其下标不存在则返回 -1。按照左闭右闭的区间定义代码可以这样写int binarySearch(vectorint nums, int target) { int left 0; int right nums.size() - 1; // 闭区间 [left, right] while (left right) { int mid left (right - left) / 2; // 防止溢出 if (nums[mid] target) { return mid; } else if (nums[mid] target) { left mid 1; // target 在右半边丢掉左半边 } else { right mid - 1; // target 在左半边丢掉右半边 } } return -1; }对应 Python 版本def binary_search(nums, target): left, right 0, len(nums) - 1 while left right: mid left (right - left) // 2 if nums[mid] target: return mid elif nums[mid] target: left mid 1 else: right mid - 1 return -1这段代码有几个细节值得展开说说。第一mid为什么用left (right - left) / 2而不是(left right) / 2因为left right在极端情况下可能溢出。比如 left 和 right 都是 10 亿级别两个加起来超过 32 位整数的上限就会变成负数导致 mid 算错。right - left一定不会超过 int 范围再除以 2 加上 left数学上等价于(left right) / 2但安全很多。Python 里整数不溢出所以问题不大但 C/Java 里这是必踩的坑。第二循环条件left right。有些教材写left right我得提醒你这取决于 right 的初始化和更新方式。我这个版本 right 初始化为nums.size() - 1区间包含 right当 left right 时区间还剩一个元素必须进入循环判断。有的版本用left rightright mid那是另一种写法后面会说。初学者最容易出的问题是“我用了left right但 right 却写mid - 1”这种组合会漏掉元素导致目标值明明在数组里却返回 -1。第三当目标值不在数组里循环最终一定会结束。为什么因为每一轮要么left变大要么right变小区间在不断收缩。当 left right 时闭区间为空循环退出返回 -1。整个过程的时间复杂度 O(log n)空间复杂度 O(1)不需要额外存储。3.2 进阶版查找第一个/最后一个等于目标值的元素实际场景里你往往不需要“随便一个位置”而是需要“第一个等于 target 的位置”或“最后一个等于 target 的位置”。比如统计一个有序数组中某个值出现的次数就需要先找下界再找上界。这时候基础版就不能直接用了因为基础版一旦命中就立刻返回它不保证返回的是第一个还是最后一个。举例来说数组是 [1, 2, 3, 3, 3, 4, 5]target 3基础版可能返回下标 2、3 或 4取决于 mid 的运气。如果我们要统计 3 的个数必须精确找到 [2, 4] 这个范围。查找第一个等于 target 的位置思路是即使nums[mid] target也不要立刻返回而是把右边界收缩到mid继续在左半边找有没有更早的相同值。这个操作实际上就是 C STL 里lower_bound的核心逻辑。代码int lowerBound(vectorint nums, int target) { int left 0, right nums.size(); while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { left mid 1; } else { right mid; } } return left; // 第一个 target 的位置 }注意这套用的是左闭右开区间。left 指向第一个满足条件的候选位置right 指向区间上限区间写作[left, right)。当nums[mid] target时mid 及左侧都可以排除所以 left 更新为mid 1否则 mid 可能是答案不能丢掉所以 right 缩到 mid。循环退出时 left right这个位置就是第一个 target 的元素下标。如果我们要找第一个等于 target 的位置只需要先调lowerBound(target)然后判断返回位置上的值是否等于 target。如果等于就返回该位置否则说明 target 不存在。查找最后一个等于 target 的元素可以先找第一个大于 target 的位置即upperBound(target)减 1 就是最后一个等于 target 的位置。upperBound和lowerBound的差别只有一个地方nums[mid] target时 left 才移动也就是等于的情况也被排除到左边区间里。int upperBound(vectorint nums, int target) { int left 0, right nums.size(); while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { left mid 1; } else { right mid; } } return left; // 第一个 target 的位置 }利用这两个函数target 的出现次数就是upperBound(target) - lowerBound(target)。这是二分查找在“区间统计”类问题里的经典应用面试和竞赛里出现频率很高。如果你手写这两个函数注意它们的本质区别只有一处比较符其他完全一样。很多人背模板时会搞混我建议你从“找第一个target”和“找第一个target”这两个语义去理解而不是死记代码。3.3 实战版查找最接近目标值的元素标题相关的热词里有一个“查找最接近的元素”这是二分查找的另一大类应用。它和“查找等于某个值”的区别是即使 target 不在数组中也要返回数组中与 target 差值最小的元素下标。最典型的问题是 LeetCode 658找到 K 个最接近的元素更基础的版本是“给定排序数组和一个 target返回最接近 target 的元素的索引”。思路其实很清晰先用二分查找找到一个“锚点”然后用两边扩散或直接比较锚点相邻位置。最直接的办法是找出第一个大于等于 target 的位置pos lowerBound(target)然后分情况如果 pos 0最接近的一定是 nums[0]如果 pos n最接近的一定是 nums[n-1]否则比较 nums[pos] 和 nums[pos-1] 哪个离 target 更近相等时按题目要求选前面或后面。C 代码可以这样写int findClosest(vectorint nums, int target) { int pos lowerBound(nums, target); // 第一个 target 的位置 if (pos 0) return 0; if (pos nums.size()) return nums.size() - 1; if (abs(nums[pos] - target) abs(nums[pos - 1] - target)) { return pos; } else { return pos - 1; } }这里有个细节如果nums[pos] - target和target - nums[pos-1]相等上面代码返回的是pos - 1。但不同题目对平局的处理要求可能不同有的要求返回更小的有的要求返回更靠前的。你需要读清楚题面必要时把相等情况单独处理。如果题目要求返回 K 个最接近的元素那就要在锚点附近用双指针从中间向两边扩展不断比较左侧元素和右侧元素哪个离 target 更近依次收进来直到收满 K 个。这个扩展过程是 O(K) 的整体复杂度 O(log n K)在数据量很大时仍然很高效。我见过不少人在这一步写的很慢因为他们没用二分直接把整个数组做了一次线性扫描。数据量小无所谓数据量一大就超时。3.4 中间值计算的溢出陷阱与整数除法行为我前面提到(left right) / 2有溢出风险这里再展开说。C 里普通 int 最大能表示约 21.47 亿两个 int 相加如果超过这个值就会溢出变成负值或产生未定义行为。在二分查找数组下标时left 和 right 正常都不会超过数组长度但如果数组是一个超大型的容器比如内存映射文件或配合size_t使用下标就可能很大。更常见的溢出场景是你把二分查找用在数值范围上比如二分答案、二分实数区间left 和 right 可能接近 INT_MAX一相加就爆了。所以标准写法永远是int mid left (right - left) / 2;而不是int mid (left right) / 2;两者数学上完全等价但前者绝对不溢出。这是一个“免费的防御性编程”成本为零收益巨大。另外注意整型除法的向下取整行为。(right - left) / 2在整数运算中会向下取整。比如 left 2right 3(3-2)/2 0mid 2。这在左闭右闭区间里是安全的因为 mid 确实落在区间内。但在某些变种写法中如果 left mid 而不是 left mid 1向下取整可能导致死循环。这点我在后面“踩坑实录”里会用具体例子说明。4. PTA函数题与在线测评的实战复盘4.1 函数题到底在考什么热词里有个“二分查找pta函数”说明很多初学者是在类似PTA拼题A这样的在线测评平台上做函数题时遇到二分查找的。PTA 的函数题通常会给出一个已经实现了一半的框架比如int Search(int T, Position L, Position R, List Lst) { // 你的代码 }或者 C 模板int BinarySearch(int a[], int n, int key) { // 待实现 }这种题表面上是考二分查找本身其实还在考阅读题目的能力。我见过很多人提交后返回段错误或答案错误根本原因不是二分逻辑不对而是没搞懂题目的输入约定。比如有的题目说“如果找到返回下标否则返回 -1”有的说“返回第一个出现的位置”还有的会要求“没找到时返回小于等于 key 的最大元素下标”。这些边界语义千差万别你必须从题面里抠清楚。函数题和完整程序题还有一个区别你不需要处理输入输出只需要实现函数接口。这意味着你需要把注意力完全放在参数的含义、返回值的约定上。我建议拿到题后先做三件事第一确认数组下标从 0 还是从 1 开始第二确认数组是升序还是降序第三确认“没找到”时函数的返回约定。把这三件事写在草稿纸上再开始写代码能避免一半以上的错误。4.2 常见WA原因速查表在线测评里出现 Wrong Answer通常都不是运气问题而是某个边界条件没有处理好。我自己整理过一个二分查找函数题的错误原因速查表分享出来供你对照错误类型典型原因排查方向返回 -1 永远触发循环条件写成left right且区间定义不一致导致单元素场景漏判检查 left/right 初始化和循环条件是否对应同一种区间写法死循环 / 超时mid 更新后 left 或 right 不变区间没有缩小检查是否存在left mid且right mid 1的组合配合向下取整导致区间长度不再减小数组越界 / 段错误返回位置为 n最后一个越界下标或访问 nums[mid-1] 时 mid 0lower_bound 返回 n 表示没找到访问前先判断边界结果差一位最接近元素的平局处理方向反了检查题目要求相等时选左侧还是右侧元素大样例出错(left right)/2溢出换成left (right - left)/2这个表里的每一行都是我在白板上排过的、或是在评测系统里真实遇到过的错误。你可以把它截图存下来做函数题之前先过一遍。4.3 本地测试用例设计写函数题最忌讳的一件事是写完了代码只在示例数据上测一遍就提交。示例数据通常太温和根本测不出边界问题。我强烈建议你每次写完二分查找都至少准备下面这组测试用例数组长度为 1[5]target 5应该返回 0数组长度为 1target 3应该返回 -1 或按约定返回数组长度为 2[1, 5]target 1 和 5 分别测试首尾命中数组长度为 2target 3测试中间缺失的场景数组全相同[2, 2, 2, 2]target 2测试第一个/最后一个位置的变体逻辑目标值小于数组最小元素、大于数组最大元素非常大的数组比如长度 100 万测试大数据是否正确、是否超时如果这些用例全过这道题大概率能拿到分数。如果出现过不了的情况就用调试器或 print 语句把每轮的 left、right、mid 都打出来看着区间收缩的过程问题通常一眼就能发现。5. 踩坑实录与排查技巧5.1 死循环是怎么产生的二分查找的死循环通常是“区间长度没有严格递减”。看这个例子查找最后一个等于 target 的元素错误版int left 0, right n - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { left mid; // 问题出在这里 } else { right mid - 1; } }假设数组是 [1, 2, 2, 3]target 2。第一轮left0right3mid 1因为(3-0)/21nums[1]2 2所以 left 1。第二轮left1right3mid 1 (3-1)/2 2nums[2]2 2left 2。第三轮left2right3mid 2 (3-2)/2 2nums[2]2 2left 2。第四轮left2right3mid 还是 2left 还是 2……循环永远跳不出去。问题出在left mid且 mid 正好等于 left区间没有缩小。修复方法有两个一是把 mid 改成向上取整即mid left (right - left 1) / 2这样当区间长度为 2 时 mid 会取右端点结合left mid也能让 left 前进二是改变更新策略用left mid 1配合别的判断。你不需要背结论只需要记住每轮循环必须保证 left 和 right 中至少有一个发生变化而且变化后区间严格缩小。写完后可以模拟一遍区间长度为 2 的情况这是最容易出错的地方。5.2 返回位置越界与 mid 相邻访问另一个高频 bug 是访问相邻位置时越界。比如查找最接近的元素代码里写了nums[pos - 1]但如果 pos 0访问下标 -1 就会段错误。这个问题在本地测试时可能测不出来因为内存布局碰巧没崩但提交到评测系统里就铁定出错。我自己养成的习惯是把“边界判断”写到访问之前。任何出现mid - 1、pos - 1、pos 1这类相邻下标访问的地方前一行先确认下标是否在合法范围内。这看起来是小事但二分查找的题目里越界错误占了分段错误的一大半。还有一个隐蔽问题当你用lowerBound得到的位置pos等于数组长度 n 时说明数组中所有元素都小于等于 target。这时如果你还去访问nums[pos]就访问到了数组末尾之后的空间。C 里这属于未定义行为可能崩也可能不崩但结果不可预期。遵循一个原则返回的下标要先判断是否在[0, n-1]范围内再决定访问。5.3 二分查找不是万能的什么时候别用最后聊一个容易被忽略的话题二分查找的适用范围比很多人想象的要窄。它的前提是“单调”也就是数组要么升序要么降序或者是某种单调函数的取值范围。如果数组不是有序的你不能直接二分必须先排序但排序是有代价的。如果数据频繁插入和删除维护有序数组本身就成了瓶颈每次插入都要移动后面的元素最坏 O(n)整体效率反而比不上平衡树。还有一类数据不适合二分分布极不均匀、且你只需要非常稀少的查找时。比如你有一个无序小数组长度为 10每次只查找一两次直接线性扫描的代码更短、更不容易错二分查找的 log₂10 ≈ 3 次比较优势在这种场景下毫无意义反而引入边界风险。算法选型永远是“在约束条件下选最合适的”不是“越高级越好”。另外浮点数的二分查找也值得提醒。对于实数域上的二分循环终止条件不能写left right因为 float 或 double 的精度有限区间长度很小之后可能无法再缩小导致死循环或不稳定。正确的做法是指定迭代次数比如循环 100 次或指定精度阈值比如right - left 1e-7。这是“二分答案”类题目的常见写法原理和整数二分一样但细节完全不同。6. 我个人在手写二分时的固定套路最后分享一个我自己的习惯供你参考。我写二分查找时不会直接写代码而是先在注释里写出三行“区间声明”然后照着声明推导代码// 区间 [left, right]闭区间目标值若存在必在此区间内 // 循环条件left right // 更新规则nums[mid] target 时 left mid 1否则 right mid - 1这三行其实是把“区间不变量”写在了代码旁边确保后面每行代码都和它自洽。写完之后我会立刻在心里模拟一个长度为 2 的数组和一个长度为 1 的数组验证循环能不能正确退出。这种习惯让我在写各种二分变体时很少犯错也推荐你尝试。另一件事尽可能复用lowerBound和upperBound而不是每次重新抠 while 循环。它们两个语义清晰、测试充分组合起来能解决查找等于、查找区间、查找最接近元素等一大堆问题。写业务代码时如果语言标准库里有现成的二分函数C 的lower_bound/upper_bound、Python 的bisect直接调用比手写更稳妥。你仍然需要会手写因为面试和竞赛不允许你调库但在工程里请相信标准库。我在实际使用中还发现很多人把二分查找当成一个“模板题”来背这是很危险的。二分查找的变体非常多比如旋转数组找最小值、二分答案求最值、二维矩阵中的二分、以及基于单调性的 include 判断。你只背一道题的代码遇到变体会发现模板各种不适用。真正有用的是你理解了“区间不变量”和“单调性”这两个底层概念这样任何变体在你眼里都是同一个东西的包装。如果你现在正在做 PTA 上的二分查找函数题或者正在准备面试中的二分查找手撕题我建议你把今天文章里的基础版、lowerBound、upperBound、findClosest 这四段代码都亲手敲一遍然后跑一遍我给的边界测试用例再上平台提交。代码这回事看十遍不如敲一遍踩过坑才记得住。