二分查找从原理到模板：边界条件与死循环避坑

聊二分查找绕不开计蒜客T1560这道题。很多人在OJ上刷二分查找专题第一道正儿八经的题目就是它。题目本身不难但能把边界条件、区间收缩、返回值这几件事彻底想明白的人并不多。我见过太多同学代码逻辑看起来没问题一跑就死循环或者答案总是差一位。这篇就把T1560从头到尾拆开讲从题意、原理到代码、避坑一次说清。这道题要解决的问题很直白给定一个已经排好序的数组然后来若干个查询每个查询给一个整数x让你快速判断x在不在数组里如果在返回它的下标。数组长度和查询次数都可能到10万级别。适合正在学基础算法、被二分边界折磨过、或者想系统梳理二分查找模板的人。看完这篇你不只能AC这一题后面遇到查找等于、查找第一个大于等于、最后一个小于等于这些变体也能顺手写出代码。1. 先别急着写代码把题意和思路理顺1.1 题目在问什么有序序列中的定位问题我按常见版本展开讲第一行两个整数 n 和 m第二行 n 个整数是已经按从小到大排好序的数组接下来 m 行每行一个查询整数 x。对每次查询要求输出 x 在这个数组中的下标如果不存在输出 -1。如果你的题面要求下标从 1 开始计数直接在答案上加 1 就行核心逻辑一模一样。注意一个关键词已经排好序。这是整道题能使用二分查找的大前提也是题目故意给好的条件。如果数组无序你第一件事是排序否则二分没有任何意义。以后做二分查找相关题目拿到数组先别急着写 while 循环先看一眼数据是不是有序的是升序还是降序有没有重复元素。这些信息直接决定你用什么模板。题目的本质是一个“定位问题”在一个长度为 n 的有序数组里反复回答“某个值在不在、在哪个位置”。查询次数 m 可以很大所以每一次查询必须尽量快。这就引出了暴力解法的致命问题。1.2 暴力为什么不行一笔账算清楚最朴素的写法是顺序查找每次查询都从数组头扫到尾遇到 a[i] x 就返回。这个写法正确性没毛病但复杂度是 O(n) 每次。如果 n 100000m 100000总比较次数就是 100000 × 100000 10^10 次。你可以在本地跑一下感受感受这个量级在普通机器上要跑几十秒在OJ上基本是稳定超时。二分查找的威力在于它把单次查找从 O(n) 降到 O(log n)。同样是 n 100000log2(100000) 约等于 17 次比较。m 次查询的总比较次数大约是 170 万次和 100 亿相比差了差不多三个数量级。这就是为什么题目一看到“有序数组 大量查询”第一反应就应该是二分。这个复杂度差异不是靠编译器优化能弥补的而是算法思路本身的差距。你写一万个 if 也救不了一个 O(n) 的循环但二分查找每比较一次就把搜索区间砍掉一半这才是它高效的根本原因。2. 二分查找的原理剖析为什么每次都能砍掉一半2.1 猜数字游戏和“区间收敛”的思想想理解二分查找先玩一个游戏我从 1 到 100 里选一个数你每次猜一个数我告诉你是大了还是小了保证在多少次以内猜中答案是 7 次。因为你每次都猜当前范围的中间值不管反馈是大了还是小了都能把候选范围缩小一半100 → 50 → 25 → 13 → 7 → 4 → 2 → 1。二分查找就是把这个游戏搬到数组上。你维护一个“当前可能包含答案”的区间 [l, r]每次取中点 mid 和查询值 x 比较。如果 a[mid] x直接命中如果 a[mid] x说明 x 只可能在中点右侧于是把左边界收缩到 mid 1如果 a[mid] x说明 x 只可能在中点左侧于是把右边界收缩到 mid - 1。这个过程最核心的一句话就是每一轮循环都把搜索区间缩小一半。所以总轮数是 log2(n) 级别而不是 n 级别。这也是它名字里“二分”的由来。你不需要记住任何花哨的技巧只需要牢牢抓住“区间不断减半”这个思想后面所有模板都是这个思想的表达。2.2 有序性才是二分的灵魂很多人把二分当成一个单纯的“查找技巧”忽略了一个前提数组必须有序。为什么有序这么重要因为在无序数组里你取中点后根本无法判断 x 到底在哪一侧。a[mid] x 的时候x 可能在左边也可能在右边信息完全没有减少区间收缩不了。有序数组相当于给了你一个“方向感”。从小到大排列时如果 a[mid] x那么 mid 左边所有元素都一定小于 x可以直接排除如果 a[mid] x那么 mid 右边所有元素都一定大于 x也可以直接排除。正是这种单调性让“砍一半”成为可能。用生活化的说法查英文字典时你不会从第一页开始翻而是先翻到中间看目标词在中间页的前面还是后面再决定往前翻还是往后翻。字典词条按字母顺序排列这个“有序性”是你能这样翻的前提。如果字典乱序你只能一页页翻到天荒地老。2.3 区间表示方式闭区间还是左闭右开二分查找的模板在网上能搜到十几种看多了容易晕。其实它们的本质区别只有一个你用什么方式表示“当前搜索区间”。最常见的两种第一种是闭区间 [l, r]初始 l 0r n - 1循环条件是 while (l r)。每次缩小区间时l mid 1 或 r mid - 1。这种写法的停止条件是 l r此时区间为空。第二种是左闭右开 [l, r)初始 l 0r n循环条件是 while (l r)。每次缩小区间时l mid 1 或 r mid。这种写法的停止条件是 l r此时区间只剩一个位置也就是答案所在。我给你的建议是选一种你最能理解的然后把它的边界行为彻底吃透。你自己开新项目时可以用任何一种但比赛和做题时别换来换去。因为每种模板的返回值含义不同混用最容易翻车。本文后面主要用闭区间 [l, r] 展开因为它最直观也最不容易越界。3. 手写二分从零到AC的最小模板3.1 mid 的计算细节与防溢出二分查找的代码短但每一行都有讲究。先看中点计算。最常见的隐患是这么写int mid (l r) / 2;问题是当 l 和 r 都很大时l r 可能溢出 int 范围造成 mid 变成负数程序直接崩溃或者陷入死循环。虽然本题 n 是 10 万级别不会触发溢出但这是一个不好的习惯。保险写法是int mid l (r - l) / 2;这个式子的意思和 (l r) / 2 完全一样但避免了先加后除可能带来的溢出。以后数据范围到 10^9、甚至更大时这个细节能救你一命。另外注意一个配合点当 l r 算出来的区间长度为偶数时mid 取的是左中位数。比如 l 0r 5(l r) / 2 2它偏左。这个特性在闭区间模板里没问题但在某些左闭右开模板里可能导致死循环。所以再次强调选一个模板别乱混。3.2 查找目标值是否存在的基础二分先写最基础版本数组里可能有多个相同的 x我只要返回任意一个下标就行找不到返回 -1。完整 C 代码如下#include iostream #include vector using namespace std; int binarySearch(const vectorint a, int x) { int l 0, r (int)a.size() - 1; while (l r) { int mid l (r - l) / 2; if (a[mid] x) { return mid; } else if (a[mid] x) { l mid 1; } else { r mid - 1; } } return -1; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorint a(n); for (int i 0; i n; i) { cin a[i]; } while (m--) { int x; cin x; cout binarySearch(a, x) \n; } return 0; }这段代码的逻辑就是前文说的三部曲相等返回小了向右大了向左。循环能退出的保证是每轮 l 和 r 的距离至少缩小 1因为无论走哪条分支要么 l 变成大于 mid 的值要么 r 变成小于 mid 的值区间不可能原地不动所以不会死循环。3.3 查找第一次出现位置记录候选再向左收缩T1560 这道“二分查找一”在计蒜客的题目序列里往往还包含一个要求如果 x 出现多次输出第一次出现的位置。这时候“返回任意一个下标”就满足不了了。思路要改成每当中点等于 x我先把这个位置记下来但不要立刻返回而是继续把右边界向左收缩看看左边还有没有更早的 x。int findFirst(const vectorint a, int x) { int l 0, r (int)a.size() - 1; int pos -1; while (l r) { int mid l (r - l) / 2; if (a[mid] x) { if (a[mid] x) { pos mid; } r mid - 1; } else { l mid 1; } } return pos; }为什么 a[mid] x 时都向右收缩因为我要找第一个等于 x 的位置所以只要中点值不小于 x真正答案只可能在中点左边或者中点本身。注意判断顺序先收缩再判断等于时记录 pos。如果把 pos 的更新放到收缩之后边界就会错。这也是很多人写变体时最容易搞混的地方。如果你不想手写这个逻辑C 标准库的 lower_bound 就是干这个事的它返回第一个不小于 x 的迭代器。想找第一个等于 x 的位置可以写成int pos lower_bound(a.begin(), a.end(), x) - a.begin(); if (pos n a[pos] x) cout pos \n; else cout -1 \n;但比赛和做题阶段我强烈建议你手写一遍因为二分查找的价值不只是“能用”而是你以后做“二分答案”题时得对区间的每一步收缩有直觉。库函数能给你答案给不了你直觉。4. 常见边界错误与避坑手册4.1 死循环是怎么产生的二分查找初学者最大的噩梦就是死循环。明明逻辑看着挺对为什么程序跑不出去大部分情况出在两处。第一处是循环条件写成 while (l r)但区间更新时用了 l mid 或 r mid 这种写法。当 l 和 r 只差 1 时比如 l 3, r 4mid 3如果走了 l mid 分支l 还是 3区间根本不缩小无限循环。第二处是 mid 取整方向问题。在左闭右开 [l, r) 模板中如果你把 mid 算成靠右的值再搭配 r mid 更新也可能出现区间不缩小的情况。怎么治一个简单粗暴的检查方法在循环体末尾打印 l 和 r看某一轮是否出现了完全相同的值。如果出现就是区间没有收缩。我个人的建议是如果你手写二分总死循环先从闭区间模板练起。闭区间 [l, r] 中只要更新时保证 l mid 1 或 r mid - 1区间长度就一定减一死循环概率大幅降低。4.2 返回值到底是 l、r 还是 mid这是另一个高频翻车点。不同二分模板在循环退出后l、r、mid 的含义完全不同。我整理了一张对照表模板初始区间循环条件停止时状态返回值常用选择闭区间[0, n-1]l rl r 1区间空依赖 pos 变量或 mid左闭右开[0, n)l rl r区间单点返回 l左开右开(-1, n)l 1 rl 1 r返回 l 或 r 视情况这张表的意思是不要觉得“反正都是答案返回哪个都一样”。闭区间模板中循环结束后 mid 变量已经失效你必须靠额外变量记录答案左闭右开模板中正确答案收敛到了 l 上返回 l 才正确。我的经验是如果你用左闭右开模板就记住一句话——“循环退出时l 指向第一个满足条件的位置”。所有变体都围绕这句话展开。用闭区间模板时就老老实实准备一个 pos 变量不要偷懒。4.3 找不到元素时怎么办题目要求不存在时输出 -1。很多初学者的代码里循环条件、数组访问全部正确但忘了处理“找不到”的情况直接输出了一个莫名奇妙的数。闭区间模板里如果整个循环跑完都没触发a[mid] xpos 就保持初始值。我习惯把 pos 初始化为 -1这样最后直接输出 pos 就能同时处理“找到”和“找不到”两种情况。别把 pos 初始化成 0否则数组第一个位置查不到时你会输出 0看起来像找到了下标 0但逻辑是错的。左闭右开模板则需要额外判断循环结束后先确认 l 在数组范围内再检查 a[l] 是否等于 x。如果 l n说明 x 比数组里所有元素都大越界了如果 a[l] ! x说明它不在数组里。两种都不能直接输出 l。4.4 数组越界与空区间判断还有个隐蔽问题当 r 被更新到 -1 时循环条件 l r 会判断为假所以不会访问 a[-1]。但如果你在循环体外面写a[l]这种访问就要小心 l 可能是 n 或 -1。比如左闭右开模板中 l 最后可能等于 n此时a[l]是越界访问必须加一个l n的判断。另外如果 n 0也就是数组为空闭区间初始是 l 0, r -1循环条件立刻不成立直接返回 -1这没问题。但你要是用左闭右开模板初始是 l 0, r 0循环条件 l r 不成立返回 l 0如果不加检查就去访问 a[0]直接崩溃。本题 n 通常大于 0但你写通用函数时要把这个边界考虑进去。5. 复杂度分析与竞赛实用技巧5.1 复杂度再算一笔账二分查找单次查询的时间复杂度是 O(log n)。具体到实现每次循环做一次比较和一次区间更新循环次数约等于 log2(n)。当 n 100000 时log2(100000) 约等于 16.6也就是说单次查询最多十七八次比较。m 次查询的总复杂度是 O(m log n)。我前面已经算过n 和 m 都在 10 万时总比较次数大约 170 万次这个量级在 C 里几乎是瞬间完成在 Python 里也完全可接受。加上存储数组本身需要的 O(n) 空间整个算法是一个时间上接近最优、空间上只存原始数据的方案。还有一个小细节二分查找是“随机访问”驱动的算法它只依赖数组下标访问不像链表那样需要顺着指针走。所以它对 CPU 缓存也比较友好实际运行速度通常比理论上算出来的还要快。这也是为什么有序数组上的查找问题二分永远是首选。5.2 输入加速关同步与快读如果你在计蒜客上提交这道题C 的 cin 和 cout 默认同步 stdio性能已经能满足 10 万级别的输入输出。但如果是 10^6 级别的数据或者遇到多组测试样例cin 就有点悬了。建议每次刷题都养成一个习惯在 main 函数最前面加两行ios::sync_with_stdio(false); cin.tie(nullptr);这两行的作用是取消 cin 与 scanf 的同步并解除 cin 和 cout 的绑定让 C 的标准输入输出不再被“保险但慢”的模式拖累。用 printf 的同学也可以继续用 scanf效果类似。Python 选手注意一个坑用 input() 一行行读在 m 很大时会明显变慢。改用 sys.stdin.buffer 读取一次性读入再按行处理能快不少。二分查找本身不是性能瓶颈输入输出往往是 Python 在简单题上超时的罪魁祸首。下面给一个 Python 手写二分的参考版本import sys def main(): data sys.stdin.buffer.read().split() n, m int(data[0]), int(data[1]) a list(map(int, data[2:2 n])) idx 2 n out [] for _ in range(m): x int(data[idx]) idx 1 l, r 0, n - 1 pos -1 while l r: mid (l r) // 2 if a[mid] x: if a[mid] x: pos mid r mid - 1 else: l mid 1 out.append(str(pos)) sys.stdout.write(\n.join(out)) if __name__ __main__: main()5.3 从这道题延伸出去二分的同一个套路T1560 只是二分查找的第一课后面还有“二分查找二”、“二分查找三”题目会从“查找等于某个值”升级到“查找第一个大于等于某个值”“查找最后一个小于等于某个值”甚至从数组查找升级到“二分答案”——比如在某个单调的函数值上二分出满足条件的最小解。这些题在代码层面几乎一模一样区别只在判断条件怎么写。你可以把“第一个大于等于 x 的下标”作为一个母模板int lowerBound(const vectorint a, int x) { int l 0, r a.size(); while (l r) { int mid l (r - l) / 2; if (a[mid] x) { l mid 1; } else { r mid; } } return l; }这个模板的思想是把查找问题转化为“找边界”。返回的 l 是第一个不满足“小于 x”的位置也就是第一个大于等于 x 的下标。有了这个母板后面所有二分变体都可以通过调整比较条件和返回值推出来。建议你把这段代码和前面的闭区间模板对照着看亲手推导一遍两个模板的每一步差异比单纯背模板有用得多。我自己的体验是二分查找这个知识点的门槛不在理解“二分”两个字而在于把每一行代码的“为什么”都搞清楚。为什么更新左边界是 mid 1为什么右边界用 mid - 1为什么循环条件是这个为什么最后返回这个变量。当你把这些问题全部回答清楚再遇到任何二分题都不会慌。我教过很多刚开始刷题的朋友最快的入门方式就是把闭区间、左闭右开和 lower_bound 三个模板各默写三遍然后自己模拟一组数据把每一步区间变化画出来。画着画着边界问题就全都明白了。