别硬算，先猜！用“二分答案”把难题变成简单的判断 - 每日分享

你有没有遇到过这种情况？
面前摆着一堆苹果，要分给几个小朋友，要求每个人拿到的重量尽量相等。你心里明明知道答案就在某个区间里，可就是不知道怎么直接算出来。
但如果你换个思路——先猜一个数，然后验证这个数行不行——问题就像魔术一样简单了。

这就是编程里一个特别实用的思想：二分答案。

一、本质：你不需要“算”答案，只需要“验证”答案

很多最优化问题难在“求最值”，但如果把它转化成“判断某个候选值是否可行”，往往就简单得多。

为什么能这么做？因为答案具有单调性。

如果要求“最大值最小”，那么候选值越大，可行性越差；
如果要求“最小值最大”，那么候选值越大，可行性越好。

就像猜数字游戏：每次猜一个中间数，根据“大了”还是“小了”不断缩小范围，最后一定能锁定目标。二分答案就是把这套玩法用在“答案空间”里。

比如说“切木棍”问题：

给你几根长度不同的木棍，要切出至少 m 根长度相同的小木棍，求这个小木棍的最大长度。

你不需要直接构造那根小木棍多长，你只需要写一个函数：

def can_cut(sticks, m, k):
    count = 0
    for s in sticks:
        count += s // k
    return count >= m

然后，让二分在答案区间里帮你找最大的 k：

while left <= right:
    mid = (left + right) // 2
    if can_cut(sticks, m, mid):
        ans = mid
        left = mid + 1
    else:
        right = mid - 1

就这么简单。

二、单调性是二分答案的命根子

如果你写完二分，发现答案不对，八成是“可行性”和“答案大小”之间的关系搞错了。

看这道题：

给定一个正整数数列和一个参数 p，定义一个数列是“完美数列”，当且仅当它的最大值 M 和最小值 m 满足 M ≤ m * p。现在要从数列中选尽可能多的数组成完美数列，问你最多能选几个。

这题不是求“某个数的最大/最小”，但它的思路同样依赖单调性：

如果你能选出 k 个数构成完美数列，那么选更少的数（比如 k-1 个）也一定可以。
所以答案满足单调性，可以二分 k（选取的数量）。

但这里你不能直接用原始数组二分，因为“完美数列”要求最大值和最小值之间的关系，所以需要先排序。

排序后，原问题变成：在一个有序数组中，能否找到一个长度为 k 的子数组，使得它的最大值 M 和最小值 m 满足 M ≤ m * p。

验证函数就可以写成：

def can_len(k):
    for i in range(n - k + 1):
        if arr[i + k - 1] <= arr[i] * p:
            return True
    return False

配合二分，完美解决。

三、一个非常容易踩的坑：验证函数的标准

二分答案的代码模板也就那么几行，真正容易错的是验证函数到底怎么写。

比如“切木棍”问题，要求“至少切出 m 根”。验证函数里用到的是：

count >= m

注意，是 >=，不是 ==。
切多了？没关系，题目只要求至少，浪费几根也行。但如果你写成了 == m，答案就会偏小，甚至错得离谱。

再看一个“猜猜乐”的模拟题，它就是用二分法来猜一个数：

格莱尔心里想一个 1~100 的整数 n，尼克每次猜一个数，根据“大了/小了”来调整。请你模拟二分猜数的过程，输出每次猜的数字，直到猜中为止。

这其实是二分查找，而不是二分答案，但思路一模一样：区间缩小靠“可行/不可行”判断。这里的判断就是“猜大了还是猜小了”。

核心代码：

left, right = 1, 100
while left <= right:
    mid = (left + right) // 2
    print(mid)
    if mid == n:
        print("成功！")
        break
    elif mid < n:
        left = mid + 1
    else:
        right = mid - 1

这是理解二分思想的“入门小菜”，也是二分答案的骨肉。

四、二分的两个方向：最大值和最小值

刚学的时候，我老搞混一个问题：left = mid + 1 和 right = mid - 1 到底什么时候用？

后来记住一句话就行了：

求最大值：可行就往右；求最小值：可行就往左。

举个例子，同样是“分苹果”这种最小值最大化问题：

有重 [9, 7, 4] 克的三个苹果，切成小块分给 3 个小朋友，每块必须整克，问每人最多能拿到多少克？

猜一个 k，如果每个苹果能切出的块数加起来 ≥ 3，说明 k 可行。
那么 k 越大越难满足，所以我们要找“可行”的最大那个 k。

当 k = 4 时：

9 // 4 = 2
7 // 4 = 1
4 // 4 = 1

总块数 2+1+1=4 ≥ 3，可行。继续猜大一点。

当 k = 5 时：

9//5=1, 7//5=1, 4//5=0

总块数只有 2 < 3，不可行。所以最大值就是 4。

验证函数极其简洁：

def can(k):
    return sum(w // k for w in weights) >= m

二分查找部分：

while left <= right:
    mid = (left + right) // 2
    if can(mid):
        ans = mid
        left = mid + 1
    else:
        right = mid - 1

就这么干净。

五、一道选择，帮你踩中核心认知

我见过这样一道题：

在二分答案算法中，以下哪个条件是必须满足的？
A. 答案具有单调性
B. 数组必须有序
C. 答案必须连续
D. 必须使用递归

正确答案是 A。

很多人会选 B，因为“二分”两个字让他们想到了“有序数组”。但二分答案和二分查找是两个不同的概念：

二分查找：在一个有序数组中找某个值，前提是数组有序。
二分答案：在一个答案区间里找最优解，前提是答案具有单调性。

所以才会有“二分答案不一定要求数据有序”的说法。
比如切木棍，木棍长度列表根本不需要有序，你照样能切，照样能二分。

还有一种说法也常被误解：

“二分答案只能用于最大值最小化问题，不能用于最小值最大化问题。”

这是错误的。
二分答案既能处理“最大值最小化”，也能处理“最小值最大化”。
只要你构造的验证函数具有单调性，那么二分的两个方向都走得通。
就像“仓库选址最小化最大距离”是往左收缩，“苹果分配最大化最小重量”是往右扩张——本质完全对称。

六、你的第一道二分答案题，可以从这开始

如果你刚刚接触这个思想，我建议你先别急着做难题。
拿“切木棍”或“分苹果”这种模板题练手，把下面的套路背熟：

确定 left 和 right
写 can(x)
while 循环二分

等你把这道题内化了，再去挑战“完美数列”这种带排序和双指针的判断函数。
你会发现，二分答案真正考验的不是二分本身，而是你怎么设计“验证函数”。
验证函数怎么写，往往取决于你对题目的理解深度。

所以，下次遇到“求最大/最小可行值”的题，别硬算，先试着：
猜一个值，写个函数验证，然后二分。
很多看起来没法直接求的问题，都能靠“猜”来解决。

关于作者

我是赵老师，持有 NOI 信息学奥赛教练证书，拥有 15 年以上的软件开发经验，从事信息学少儿编程教学已有 8 年时间。

这些年累计帮助多名学生通过编程特长升入自己心仪的目标学校。

如果你在编程学习上有任何疑问，欢迎联系我：18620372957（微信同号）