二分的名声很怪入门书说它简单可一到手写left right还是left right、mid 1还是mid、要不要上取整马上就乱。我打算法竞赛那几年整数二分是唯一一个背了又忘、忘了又背的知识点直到后来想明白一件事——整数二分找的从来不是“一个数”而是一个分界点。这篇文章不打算给你灌“二分很简单”的鸡汤而是从分界点的视角把整数二分的原理、两套常用模板、边界细节和调试方法一次讲透让准备面试、搞竞赛或者日常写业务代码的读者都能真正敢手写、写不错。1. 整数二分到底在找什么分界点比模板更重要1.1 “有序数组里找 target”只是整数二分的特例我们最早接触二分基本都是在“有序数组”里找一个数。假设数组[1, 3, 5, 7, 9]你要找5于是每次拿中间值跟目标比大小大了往左、小了往右。这套思路本身没问题但如果你只会这么想遇到变体题就抓瞎了。更本质的理解方式是这样的给定一个判断条件check(i)它在下标序列上满足如下形式左侧是连续的false右侧是连续的true下标 0 1 2 3 4 5 check F F F T T T二分能跑的真正前提不是“数组数值有序”而是check 的结果有序单调。我们要找的就是false和true之间的那个分界点。理解了这一点“有序数组找 target”其实只是check(i) (nums[i] target)这个条件的特例我们的目标是找第一个满足 target的下标。我见过很多同学背了一堆二分模板遇到“第一个大于等于 target 的位置”“最后一个小于 target 的位置”就套错就是因为脑子里只有“比较大小”没有“找分界点”。一旦把问题翻译成“找 F...F T...T 的分界”方向感立刻就有了。1.2 整数二分比浮点二分难在哪离散边界不能“差不多”浮点二分通常这么写double l 0, r 1e9; for (int i 0; i 100; i) { double mid (l r) / 2; if (check(mid)) r mid; else l mid; }浮点二分的区间长度一直除以 2很快缩到足够小不会死循环。但整数二分是离散的区间长度必须变成整数而且每一步都必须让区间长度严格减少否则就会出现l mid后 mid 还等于 l 的死循环。打个比方猜 1 到 100 之间的整数对方告诉你“大了/小了”。如果你回答“我猜 50”对方说“大了”那你知道答案在 1 到 49下一条你必须从 1 到 49 里再猜一个整数而不能继续猜 49.5。整数域上没有“无限接近”这个概念所以mid的取整方向和l/r的更新方式必须配对好。这也是不同模板全部区别的根源。下面我把两套最常用的整数二分模板拆开讲。2. 两个核心模板边界更新方式与死循环的根源2.1 模板 A找第一个满足 check(mid) 的位置适用条件check结果呈F F ... F T T ... T。我们要从左往右找到第一个T。标准写法// 在 [0, n] 范围内找第一个满足 check(mid) 的下标 // 注意r 初始化为 n表示“右侧开区间”答案最大可以是 n int l 0, r n; while (l r) { int mid l (r - l) / 2; // 下取整 if (check(mid)) r mid; else l mid 1; } // 结束时 l r就是答案为什么mid要下取整因为当区间为[l, r)时下取整能让 mid 偏向左边配合l mid 1保证每一轮区间长度都至少减少 1。再看更新逻辑如果check(mid)为 true说明分界点不可能在 mid 右边mid 自己可能是第一个 true所以右边界收缩为r mid如果check(mid)为 false说明 mid 及 mid 左边全是 false左边界要前进到l mid 1。拿[F, F, T, T]来模拟l0, r4mid2check(2)truer2下一轮 mid1check(1)falsel2此时 lr2正好是第一个 T。2.2 模板 B找最后一个满足 check(mid) 的位置适用条件check结果呈T T ... T F F ... F。我们要从右往左找到最后一个T。标准写法// 在 [-1, n-1] 范围内找最后一个满足 check(mid) 的下标 // 注意l 初始化为 -1表示“左侧开区间”答案最小可以是 -1 int l -1, r n - 1; while (l r) { int mid (l r 1) / 2; // 上取整这是关键 if (check(mid)) l mid; else r mid - 1; } // 结束时 l r就是答案这里最容易翻车的就是mid为什么必须上取整。考虑一种情况l 2, r 3假设check(2) true。如果mid下取整mid (2 3) / 2 2发现check(2) true于是l mid 2。区间依然是[2, 3]下一轮还是这样死循环。上取整后mid (2 3 1) / 2 3l至少能前进到 3区间缩小问题解决。更新逻辑也比较对称check(mid)为 true说明 mid 自己可能是最后一个 true左边也可能有所以l midcheck(mid)为 false说明 mid 及右边全是 false右边界收缩为r mid - 1。2.3 两套模板怎么选一张表说清楚单调形态目标mid 取整更新方式初始化F...F T...T第一个 true下取整true: rmidfalse: lmid1l0, rnT...T F...F最后一个 true上取整true: lmidfalse: rmid-1l-1, rn-1初始化里的rn和l-1都是开区间哨兵用来处理“全部 false”或“全部 true”的边界情况。比如模板 A 如果check(0)到check(n-1)全是 false答案就不是一个合法下标而是n表示不存在模板 B 如果全是 true答案就是n-1如果全是 false答案就是-1。这种开区间技巧能帮你少写很多特判。3. 在有序数组里手写 lower_bound / upper_bound3.1 用模板 A 直接实现有序数组的查找看似基础其实很适合验证上面的模板。C 标准库里lower_bound返回第一个 target的位置upper_bound返回第一个 target的位置。手写实现直接用模板 Aint my_lower_bound(vectorint nums, int target) { int l 0, r nums.size(); while (l r) { int mid l (r - l) / 2; if (nums[mid] target) r mid; else l mid 1; } return l; } int my_upper_bound(vectorint nums, int target) { int l 0, r nums.size(); while (l r) { int mid l (r - l) / 2; if (nums[mid] target) r mid; else l mid 1; } return l; }两个函数长得几乎一样唯一的差别就是判断条件是 target还是 target。这也解答了很多人的疑问“lower_bound 为什么不是直接找等于”因为 lower_bound 的本质就是找第一个让nums[i] target成立的位置它天然返回了 target 可能插入的位置而不是是否存在。mid l (r - l) / 2而不是(l r) / 2是为了防止l r溢出。在 C 的 int 范围内这种事不太容易遇到但如果你在做数值范围很大的题或者从 Java 转过来这个习惯值得保留。3.2 利用 lower_bound / upper_bound 求相等区间一旦手写了 lower_bound 和 upper_bound找出目标值 target 在有序数组中出现的连续区间就很简单int left my_lower_bound(nums, target); int right my_upper_bound(nums, target); // target 的区间是 [left, right - 1] // 如果 left right说明 target 不存在比如nums [1, 2, 2, 2, 3, 4]target 2函数返回下标含义lower_bound1第一个 2 的元素upper_bound4第一个 2 的元素区间[1, 3]三个 2如果你想只用模板 A 找“最后一个等于 target”的位置也可以这么算upper_bound(target) - 1也就是找到第一个 target的位置再减一。不过要小心减完可能越界所以要先判断返回值。这段内容看起来简单但它把“二分查找”和“边界模板”的关系打通了。以后再遇到 LeetCode 34 这种“找第一个和最后一个位置”的题你不是背题解而是直接推导第一次出现是第一个 target最后一次出现是第一个 target的前一位。3.3 与库函数对照验证的正确姿势写模板题时我强烈建议你拿标准库做对拍。比如写一个 Python 的bisect_left或 C 的std::lower_bound再拿你手写的版本跑随机数据。下面伪码思路很有用import random for _ in range(10000): arr sorted(random.randint(0, 20) for _ in range(random.randint(1, 20))) target random.randint(0, 20) a my_lower_bound(arr, target) b bisect_left(arr, target) assert a b这种“随机对拍”的验证思路不仅适用于二分几乎所有边界敏感的算法题都该用。跑几千组随机用例比自己盯着代码看十分钟有效得多。4. 二分答案把“最优化”变成“判定”4.1 什么时候能对答案二分整数二分最有价值的地方不是有序数组查找而是二分答案。很多题目让求“最大值最小”“最小值最大”“最长/最短可行值”一看就头疼但如果能构造一个判定函数check(x)且check(x)的结果随 x 单调变化就能把最优化问题转成判断题。核心思路对答案所在的整数范围二分每次用mid模拟一遍判断 mid 是否可行。比如经典的“切木头”给你 n 根木头长度要切成至少 k 段长度相同的小段问每段最长能是多少。定义check(len) (所有木头能切出的总段数 k)。len 越大能切出的段数越少所以check(len)随 len 增大从 true 变成 false也就是T...T F...F形态。这时候要用模板 B找最后一个 true。再比如更经典的“跳石头”问题要从起点跳到终点途中有若干块可选的石头可以移走 M 块要求最小跳跃距离尽量大。这题的check(x)可以设计为“能否通过移走不超过 M 块石头让任意相邻落脚点之间的距离都 x”。x 越小越容易满足x 越大越难又是T...T F...F形态。4.2 一个直接套用的代码骨架二分答案的代码结构基本固定bool check(int x) { // 根据题意判断 x 是否可行 } int solve() { int l get_min_possible_answer(); int r get_max_possible_answer(); while (l r) { int mid (l r 1) / 2; if (check(mid)) l mid; else r mid - 1; } return l; }注意这里我用了上取整和模板 B对应的是check越往左越 true 的情况。如果你发现你的check越往右越 true就换成模板 Awhile (l r) { int mid l (r - l) / 2; if (check(mid)) r mid; else l mid 1; }很多初学者卡在“到底用哪个模板”本质上就是没先分析 check 的单调方向。我自己的习惯是先在注释里写出这个题 check 的单调形态再选模板。比如写// check(x): x 越大越不可能完成所以是 T...T F...F用模板 B这一步做完后面基本不会乱。4.3 边界初始化最容易踩的坑二分答案的边界初始化不能拍脑袋。比如上面切木头的例子答案可能是 0也可能很大那么l可以取 0r要先算出可能的最大值通常是最长木头的长度而不是数组长度。如果题目要求输出最长长度边界写错会导致两种典型后果一是 mid 过大check(mid)返回 false 后把右边界收到 mid-1结果漏掉正确答案二是 mid 过小答案域没覆盖完最终输出偏小。我见过有人把右边界的r直接用1e9这种大数也没问题只要check(mid)在 mid 过大时不会崩溃、不会溢出。但能用有意义的上下界尽量用有意义的因为越界检查、log 次数都更可控。还有一个容易忽略的点如果 check 函数内部涉及累加、乘法mid很大时可能爆 int。这时候要用long long或者直接在check里提前 return false避免无意义计算。二分答案题经常藏这种数值陷阱WA 了别只盯二分模板也要检查数据范围。5. 旋转数组和峰值查找二分不止 check(mid)5.1 旋转有序数组找最小值不用固定 target 也能二分LeetCode 153 题是个很好的例子数组[4,5,6,7,0,1,2]是一个有序数组在某处旋转得到的要求找最小值。这里没有 target也没有明显的“第一个 target”条件但依然能二分。最稳妥的做法是用nums[mid]和nums[r]比较int findMin(vectorint nums) { int l 0, r nums.size() - 1; while (l r) { int mid l (r - l) / 2; if (nums[mid] nums[r]) l mid 1; else r mid; } return nums[l]; }为什么和nums[r]比如果nums[mid] nums[r]说明mid在旋转点的左边最小值一定在mid 1到r之间所以l mid 1如果nums[mid] nums[r]说明mid到r这段是单调递增的最小值不可能在mid右边所以r mid。这个写法本质上仍然是在收缩“最小值所在区间”只是判定条件不是某个check(mid)的 bool而是基于数组局部大小关系的判断。它的单调性来自旋转数组“前半段大于后半段”的结构特征。如果数组里有重复元素比如[1,1,1,0,1]上面的比较在nums[mid] nums[r]时不好判断方向最坏情况下复杂度退化成 O(n)。这种“看起来像二分但条件不足”的情况也是面试里经常拿来追问的点。5.2 峰值查找沿着上升方向收缩LeetCode 162 题要求在相邻元素不相等的前提下找到任意一个峰值也就是nums[i] nums[i1]。int findPeakElement(vectorint nums) { int l 0, r nums.size() - 1; while (l r) { int mid l (r - l) / 2; if (nums[mid] nums[mid 1]) r mid; else l mid 1; } return l; }这里其实是一种贪心思想如果nums[mid] nums[mid1]说明mid处在上升趋势中峰值一定在右侧如果nums[mid] nums[mid1]说明mid处在下降趋势中峰值一定在左侧包括 mid 自己。这样不断向“一定有峰值”的方向收缩。这种题和前面模板 A/B 不太一样它没有显式的 check 单调序列但二分区间收缩的逻辑完全一致每一步都能砍掉一半不可能是答案的区域。所以我说二分是一种区间收缩思想不只是一套死循环模板。5.3 什么时候不能二分看到这里你可能会想“感觉什么都能二分”。不是的二分的前提是能根据 mid 的信息排除掉一侧区间。如果数组无序且没有任何额外约束比如让你在一个完全乱序的数组里找一个等于 target 的下标就不能二分因为你无法判断 target 在 mid 的左边还是右边。刷题时遇到“二分变体”先问自己三个问题答案可能落在哪个区间范围取一个 mid能不能判断答案在 mid 左侧还是右侧判定条件在若干轮后还能不能继续生效三个问题都能回答再动手写答不上来就老老实实想其他算法。6. 我踩过的整数二分边界坑以及一套防坑调试法6.1 死循环产生的三个典型原因我最早写模板 B习惯性地写成int mid (l r) / 2; if (check(mid)) l mid; else r mid - 1;然后在l 3, r 4时check(3)为 true程序永远卡在 l3 出不来。这是最经典的死循环原因——使用下取整却执行l mid。第二个典型原因是初始化把开区间哨兵搞错。比如模板 A 里把r初始化为n-1如果整个数组都不满足条件最后返回的可能是n-1但这个下标并不满足 check语义就错了。第三个原因是 check 函数内部访问了不存在的下标。二分答案时mid可能取到答案域之外的值如果你在 check 里直接拿 mid 当数组下标很容易越界。比如l0, rn的模板 Amid 最多等于n-1但如果你把范围写成了[0, n]里的 n又用nums[mid]在 mid 接近 n 的时候就越界了。6.2 用日志法和随机对拍快速定位问题死循环和越界这类问题肉眼看不出来上日志最快。我自己在调试二分时会在循环里临时加一行while (l r) { int mid l (r - l) / 2; printf(l%d r%d mid%d check%d\n, l, r, mid, check(mid)); if (check(mid)) r mid; else l mid 1; }一旦进入死循环打印出的 l、r、mid 会反复出现同一组值一眼能看出是 mid 没有变化还是 check 结果和预期不符。更系统的验证方式是随机对拍。模板写完先别急着交拿一个复杂度低但绝对正确的暴力函数做对照。以手写 lower_bound 为例暴力版本就是遍历数组找第一个 target 的位置。然后随机生成几百组有序数组和 target比较二分结果和暴力结果。只要有一组不一致立刻知道代码哪里错了还能用那组数据缩小排查范围。6.3 一种更不容易死循环的“开区间 哨兵”写法如果你觉得上面两套模板还是要记我分享一下我个人最常用的另一种写法它在很多“找分界点”的场景下更不容易死循环int l 0, r n; // 假设我们想找最后一个 check 为 true 的位置 // 约定 l 是“已知为 true 的位置”r 是“第一个未知/不为 true 的位置” while (l 1 r) { int mid (l r) / 2; if (check(mid)) l mid; else r mid; } // 循环结束后l 是最后一个 check 为 true 的位置这里的关键是把l和r当成两个哨兵l表示已经确定满足条件r表示不满足或哨兵边界。循环条件l 1 r保证在 l 和 r 之间至少还有一个数需要判断mid 永远在 l 和 r 中间因此l mid或r mid都能让间隔缩小不会死循环。它的缺点是需要保证初始l和r落在正确的“真/假”区域中。比如你要找“最后一个满足 check 的位置”就得保证check(l)true、check(r)false如果做不到需要插入哨兵或者在循环后特判。这也是为什么这种写法适合二分答案因为答案域两端往往天然有“不可能”的边界。这个写法和前面模板 B 本质一样只是显式用两个哨兵逼近分界点对新手更友好因为它不用记“上取整”。我自己做二分答案题时经常用它尤其是 check 比较难写的时候能让注意力集中在 check 上而不是边界上。7. 从模板到实战我用这个思路做过的三道经典题7.1 LeetCode 34在排序数组中查找元素的第一个和最后一个位置思路用模板 A 分别实现 lower_bound 和 upper_bound然后判断left是否有效且等于 target。如果left nums.size() || nums[left] ! target直接返回[-1, -1]否则返回[left, right - 1]。这道题就是第三章的实战版。难点不在二分本身而在你能否快速意识到“第一次出现”和“最后一次出现”是两个不同的分界条件。7.2 洛谷 P2678 跳石头题目给出一段距离 Ln 块石头位置可移除 m 块求最短跳跃距离的最大值。这是非常典型的“最小值最大化”check 函数需要模拟跳石头过程统计为了满足“任意相邻落脚点距离 mid”最少要移除多少块石头。如果移除数量 m则 mid 可行。这个 check 写起来要小心要模拟从上一块保留石头到下一块的跳跃最后还要检查最后一段到终点的距离。很多人在“起点、终点不能移除”这个细节上犯错导致 check 统计错误二分写得再好也没用。7.3 POJ 2456 Aggressive cows最大化最近距离同样是“最大值最小/最小值最大”的经典题。给定牛棚位置要求安排 c 头牛使任意两头牛的最近距离尽量大。check(distance) 表示“能否每隔至少 distance 距离放下所有牛”distance 越大越难满足所以也是T...T F...F用模板 B。这类题我建议做三到五道不要贪多。做完之后你会有个很明显的感受整道题的重心根本不在二分而在 check 函数怎么写。二分只是把 O(N) 的可行性判断跑 O(log MAX) 遍而已。如果 check 写得糊里糊涂模板选得再好也白搭。现在我再写二分习惯是先把注释写好check(mid)的单调方向是 F...F T...T 还是 T...T F...F然后决定用哪个模板、mid 怎么取整、哨兵初始值放多少。这个习惯帮我解决了不少面试和竞赛里看似刁钻的二分变体题。如果你也经常在整数二分上翻车不妨从下一道题开始先别急着敲代码把分界点和方向想清楚再动键盘你会发现自己比想象中更擅长二分。