第12篇-二分答案法-当答案不好求时如何反向搜索

概述：为什么学完二分查找后一定要学二分答案

上一篇我们讲了二分查找。
最经典的二分查找，是在一个有序数组里查找目标值。

但在算法题里，还有一类更隐蔽、更高频的二分：

题目不是让你在数组里找某个数，而是让你求一个最小值或最大值。

例如：

• 最少需要多少天才能完成任务
• 最小的运输能力是多少
• 最大的可行距离是多少
• 最小的速度是多少
• 最多能切出多长的绳子

这些题看起来并不像传统二分查找，因为数组可能根本不是有序数组。
但它们有一个共同特征：

答案本身存在一个有序的可行区间。

这就是二分答案法。

这篇文章的目标，是帮你建立下面几件事：

1. 什么是二分答案
2. 为什么“求最值”可以变成“判定可行”
3. 如何设计check函数
4. 如何判断应该找最小可行值还是最大可行值
5. 如何用模板解决经典题

学完这篇，你应该能把一类“答案不好直接求”的最值问题，转化成“给定一个答案，判断它是否可行”的二分模型。

核心概念：什么是二分答案法

普通二分查找通常是在数组下标上二分：

在 nums 中找 target

而二分答案法是在“答案范围”上二分：

答案可能在 [left, right] 中

每次取一个中间答案mid，然后问一个问题：

如果答案是mid，能不能完成题目要求？

如果能，就说明mid是一个可行答案；
如果不能，就说明mid不可行。

然后根据可行性继续缩小答案范围。

一个直观例子

假设题目问：

最小速度是多少，才能在规定时间内吃完所有香蕉？

速度越快，越容易完成；
速度越慢，越不容易完成。

如果速度10可以完成，那么速度11、12、13通常也都可以完成。
如果速度3不可以完成，那么速度1、2通常也都不可以完成。

这就形成了一个非常典型的单调结构：

速度： 1 2 3 4 5 6 7 8 9 10 11 结果： 否 否 否 否 否 是 是 是 是 是 是

题目要求的是：

第一个可行速度

这就可以二分。
二分答案不是在原数组里找值，而是在答案范围里找第一个可行值或最后一个可行值。

原理：为什么“求最值”可以变成“判定可行”

很多最值问题之所以难，是因为答案不好直接算出来。

比如：

一艘船每天最多运多少重量，才能在D天内运完所有包裹？

你很难一眼看出最小运载能力是多少。
但是如果别人给你一个能力值capacity，你可以比较容易地判断：

用这个capacity能不能在D天内运完？

这就是二分答案的核心转换：

直接求最优答案很难 -> 判断某个答案是否可行比较容易 -> 在答案范围上二分

可行性必须具有单调性

二分答案能成立，关键在于判定结果要有单调性。

常见有两种情况。

第一种：找最小可行值。

不可行 不可行 不可行 可行 可行 可行

目标是找到第一个可行。

第二种：找最大可行值。

可行 可行 可行 不可行 不可行 不可行

目标是找到最后一个可行。

如果判定结果一会儿可行、一会儿不可行，没有清晰的单调性，就不能直接用二分答案。

二分答案的本质，是把“直接求最优值”转化为“判断某个候选答案是否满足条件”。

二分答案的三件套：范围、判定、收缩

做二分答案题时，不要一上来就写代码。
先问自己三个问题。

1. 答案范围是什么

二分答案首先要确定：

left 和 right 分别是多少？

例如：

• 最小速度：最小可能是1，最大可能是数组最大值
• 最小运载能力：最小可能是单个最大包裹重量，最大可能是所有包裹总重量
• 最大距离：最小可能是0或1，最大可能是最大坐标差

答案范围如果定错，后面的二分就没有意义。

2.check(mid)怎么写

check(mid)是二分答案的灵魂。

它负责回答：

当候选答案是 mid 时，是否满足题目要求？

常见写法：

privatestaticbooleancheck(intmid){// 根据题意模拟或统计// 返回 mid 是否可行}

3. 可行后往哪边收缩

如果题目要求最小可行值：

mid 可行，说明答案可能是 mid，也可能更小

所以收缩右边界。

如果题目要求最大可行值：

mid 可行，说明答案可能是 mid，也可能更大

所以收缩左边界。

二分答案题先定答案范围，再写判定函数，最后根据“找最小还是找最大”决定边界怎么收缩。

模板一：寻找最小可行值

最常见的二分答案模型是：

找到满足条件的最小值。

它的判定结果通常长这样：

false false false true true true

我们要找的是第一个true。

标准模板

publicstaticintbinarySearchMinAnswer(intleft,intright){intans=right;while(left<=right){intmid=left+(right-left)/2;if(check(mid)){ans=mid;right=mid-1;}else{left=mid+1;}}returnans;}

为什么可行时要往左找

如果mid已经可行，说明：

mid 是一个候选答案

但题目要求的是最小可行值，所以还要继续看看更小的值能不能行。

因此：

ans=mid;right=mid-1;

这和上一篇讲的“查找左边界”非常像。

找最小可行值时，check(mid)为true要记录答案，并继续向左搜索。

模板二：寻找最大可行值

另一类题目要求：

找到满足条件的最大值。

它的判定结果通常长这样：

true true true false false false

我们要找的是最后一个true。

标准模板

publicstaticintbinarySearchMaxAnswer(intleft,intright){intans=left;while(left<=right){intmid=left+(right-left)/2;if(check(mid)){ans=mid;left=mid+1;}else{right=mid-1;}}returnans;}

为什么可行时要往右找

如果mid可行，而题目要求最大可行值，说明：

答案至少可以达到 mid

所以还要尝试更大的值：

ans=mid;left=mid+1;

找最大可行值时，check(mid)为true要记录答案，并继续向右搜索。

经典例题一：爱吃香蕉的最小速度

题目大意：

有若干堆香蕉piles，每小时可以吃k根，吃完一堆后这一小时不能继续吃下一堆。给定小时数h，求最小的k，使得能在h小时内吃完所有香蕉。

例如：

piles = [3, 6, 7, 11] h = 8

答案是：

4

为什么可以二分答案

速度k越大，越容易在h小时内吃完。
速度k越小，越不容易完成。

所以可行性是单调的：

慢速度：不可行 快速度：可行

这是典型的“找最小可行值”。

答案范围怎么定

最小速度：

1

最大速度：

max(piles)

因为如果每小时能吃掉最大那一堆的数量，那么每一堆最多一小时就能吃完。

check(k)怎么写

给定速度k，计算吃完所有香蕉需要多少小时。

一堆pile需要的小时数是：

ceil(pile / k)

在整数里可以写成：

(pile+k-1)/k

代码实现

publicstaticintminEatingSpeed(int[]piles,inth){intleft=1;intright=0;for(intpile:piles){right=Math.max(right,pile);}intans=right;while(left<=right){intmid=left+(right-left)/2;if(canFinish(piles,h,mid)){ans=mid;right=mid-1;}else{left=mid+1;}}returnans;}privatestaticbooleancanFinish(int[]piles,inth,intspeed){longhours=0;for(intpile:piles){hours+=(pile+speed-1)/speed;}returnhours<=h;}

为什么hours用long

如果数据范围比较大，累加小时数可能超过int。
为了避免溢出，判定函数里用long更稳妥。

时间复杂度：

O(n log m)

其中n是香蕉堆数，m是最大香蕉堆大小。

空间复杂度：

O(1)

最小速度不好直接求，但给定一个速度后很容易判断能不能完成，所以可以二分速度。

经典例题二：在 D 天内送达包裹的能力

题目大意：

给定包裹重量数组weights，包裹必须按顺序装船。每天船最多运capacity重量，求在days天内运完所有包裹所需的最小运载能力。

例如：

weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] days = 5

答案是：

15

为什么可以二分

运载能力越大，需要的天数越少，越容易完成。
运载能力越小，需要的天数越多，越不容易完成。

所以这也是：

找最小可行 capacity

答案范围怎么定

最小运载能力不能小于最重的包裹：

max(weights)

否则这个包裹永远装不上船。

最大运载能力可以是所有包裹总重量：

sum(weights)

这样一天就能运完。

代码实现

publicstaticintshipWithinDays(int[]weights,intdays){intleft=0;intright=0;for(intweight:weights){left=Math.max(left,weight);right+=weight;}intans=right;while(left<=right){intmid=left+(right-left)/2;if(canShip(weights,days,mid)){ans=mid;right=mid-1;}else{left=mid+1;}}returnans;}privatestaticbooleancanShip(int[]weights,intdays,intcapacity){intusedDays=1;intcurrent=0;for(intweight:weights){if(current+weight>capacity){usedDays++;current=0;}current+=weight;}returnusedDays<=days;}

判定函数怎么理解

canShip做的是一次模拟：

1. 从前往后装包裹
2. 当前天能装就继续装
3. 装不下就换到下一天
4. 最后判断使用天数是否不超过days

注意题目要求包裹按顺序运输，所以不能排序，也不能随便重排包裹。

运载能力越大越容易满足天数限制，因此可以在能力范围上二分最小可行值。

经典例题三：分割数组的最大值

题目大意：

给定非负整数数组nums和整数k，将数组分成k个非空连续子数组，使得这k个子数组各自和的最大值最小，返回这个最小值。

例如：

nums = [7, 2, 5, 10, 8] k = 2

一种最优分割是：

[7, 2, 5] 和 [10, 8]

最大子数组和是：

18

这题为什么是二分答案

题目要求的是：

让“最大子数组和”尽量小

这个答案很难直接构造。
但如果给定一个上限limit，我们可以判断：

是否能把数组分成不超过k段，并且每段和都不超过limit？

如果limit越大，越容易满足；
如果limit越小，越难满足。

所以这是典型的“找最小可行上限”。

答案范围

下界：

max(nums)

因为任何一段都至少要容纳一个元素。

上界：

sum(nums)

因为最极端情况下，整个数组作为一段。

代码实现

publicstaticintsplitArray(int[]nums,intk){intleft=0;intright=0;for(intnum:nums){left=Math.max(left,num);right+=num;}intans=right;while(left<=right){intmid=left+(right-left)/2;if(canSplit(nums,k,mid)){ans=mid;right=mid-1;}else{left=mid+1;}}returnans;}privatestaticbooleancanSplit(int[]nums,intk,intlimit){intcount=1;intsum=0;for(intnum:nums){if(sum+num>limit){count++;sum=0;}sum+=num;}returncount<=k;}

为什么count <= k就可行

如果在limit限制下，可以分成不超过k段，那么一定可以继续把某些段拆开，变成正好k段。
因为数组元素是非负数，拆开不会让某一段的和变大。

所以判断条件写：

returncount<=k;

当目标是“最小化最大值”时，经常可以二分这个最大值上限。

经典例题四：最大化最小距离

前面几个例子都是找最小可行值。
再看一类相反的题：找最大可行值。

题目大意：

有若干位置position，要放置m个球，要求任意两个球之间的最小距离尽量大，返回这个最大距离。

例如：

position = [1, 2, 3, 4, 7] m = 3

答案是：

3

可以放在：

1, 4, 7

为什么可以二分距离

如果最小距离要求很小，比如1，容易放下。
如果最小距离要求很大，比如10，可能放不下。

所以判定结果是：

可行 可行 可行 不可行 不可行

我们要找的是：

最后一个可行距离

也就是最大可行值。

代码实现

importjava.util.Arrays;publicstaticintmaxDistance(int[]position,intm){Arrays.sort(position);intleft=1;intright=position[position.length-1]-position[0];intans=1;while(left<=right){intmid=left+(right-left)/2;if(canPlace(position,m,mid)){ans=mid;left=mid+1;}else{right=mid-1;}}returnans;}privatestaticbooleancanPlace(int[]position,intm,intdistance){intcount=1;intlast=position[0];for(inti=1;i<position.length;i++){if(position[i]-last>=distance){count++;last=position[i];}}returncount>=m;}

判定函数为什么用贪心

给定最小距离distance后，我们只需要判断能不能放下m个球。

最自然的策略是：

1. 第一个球放在最左边
2. 后面的球尽量往左放
3. 只要和上一个球距离足够，就放一个

这种贪心能让后续剩余空间尽量大，所以适合做可行性判断。

时间复杂度：

O(n log n + n log d)

其中d是最大位置差。

当要求“最大化最小值”时，经常可以二分这个最小距离，并用贪心判断是否可行。

二分答案常见题型总结

二分答案题常常伪装成各种不同题目，但底层结构很相似。

你会发现，二分答案经常出现在这类关键词里：

• 最小化最大值
• 最大化最小值
• 最少需要多少
• 最大可以多大
• 能否在限制内完成
• 给定条件下求最优阈值

看到“最小的最大值”或“最大的最小值”，要优先考虑能不能二分答案。

如何设计check函数

二分答案真正难的地方，往往不是外层二分，而是check函数。

设计check时，可以按下面几个步骤来。

1. 明确mid的含义

先把mid翻译成题目语言：

• mid是速度
• mid是容量
• mid是距离
• mid是时间
• mid是最大段和上限

如果你说不清mid代表什么，后面的判定函数一定会乱。

2. 明确返回值含义

check(mid)最好统一表示：

mid 是否可行

也就是：

returntrue;// mid 可以满足题目条件returnfalse;// mid 不能满足题目条件

不要一会儿表示“太大”，一会儿表示“太小”，否则外层边界非常容易写反。

3. 用模拟、贪心或计数完成判断

常见的check写法包括：

• 模拟过程：比如运输包裹需要几天
• 贪心放置：比如能否放下足够多的球
• 计数统计：比如某个长度能切出多少段
• 累加计算：比如某个速度下需要多少时间

4. 保证check本身不要太慢

二分外层会执行大约：

log(answerRange)

次。
如果check每次是O(n)，整体通常就是：

O(n log answerRange)

这是很常见、也很可接受的复杂度。

先明确mid在题目中的含义，再用模拟、贪心或计数判断它是否可行。

易错点：新手写二分答案最容易踩的坑

1. 没有证明单调性就强行二分

二分答案必须有单调性。
如果check(mid)的结果不是连续的可行或不可行区间，二分就不成立。

2. 答案范围定得太窄

比如运送包裹时，下界必须是：

max(weights)

如果下界写成1，虽然有时也能跑，但会做很多无效判断；
如果上界写小了，可能直接漏掉正确答案。

3. 分不清找最小还是找最大

这是边界写反的主要原因。

• 找最小可行值：可行时往左收缩
• 找最大可行值：可行时往右收缩

4.check返回值含义不统一

建议始终让check(mid)表示：

mid 是否可行

不要让它表示“mid 是否太大”或“mid 是否太小”，这样更容易和模板对应。

5. 整数向上取整写错

常见场景：

ceil(a / b)

在整数中可以写成：

(a+b-1)/b

这在速度、时间、批次数计算里非常常见。

6. 累加结果没有考虑溢出

如果数组元素很大，累加和、时间、工作量可能超过int。
判定函数里可以根据数据范围使用long。

7. 忘记题目要求连续或顺序

比如分割数组、按顺序运包裹，不能随意排序。
如果题目要求顺序，check只能按原顺序模拟。

8. 最大可行值题仍然套最小模板

像最大化最小距离，check(mid)为true时应该尝试更大的距离：

left=mid+1;

如果写成right = mid - 1，就会变成找最小可行值，方向完全错。

9. 没有手动验证边界值

二分答案很容易在答案刚好是下界或上界时出错。
写完后至少用这几种情况手动跑一遍：

• 最小答案就是left
• 最大答案就是right
• 数组只有一个元素
• 所有限制刚好卡住

复杂度总结：二分答案通常怎么算

二分答案的复杂度一般由两部分组成：

二分次数 * 每次 check 的代价

如果答案范围长度是R，每次判定需要扫描数组一次，那么时间复杂度通常是：

O(n log R)

例如：

空间复杂度通常是：

O(1)

如果需要排序，排序本身会带来额外时间：

O(n log n)

例如最大化最小距离这类题，通常要先对位置排序。

二分答案的总时间取决于答案范围能二分多少次，以及每次判定函数需要多少代价。

总结

二分答案的本质，是在答案上做二分查找。
二分答案法的核心，就是把难以直接求出的最优答案，变成一个可以反复判定并缩小范围的搜索问题。
当你真正掌握这套思路后，很多看起来不像二分的题，都会变成：

答案范围 + check 函数 + 边界收缩

下一次再看到“最小速度”“最小容量”“最大距离”“最小最大值”这类题时，就要主动想一想：
这个答案本身，能不能被二分？