二分答案：把最优化问题转化为判定问题

什么是二分答案？

在日常算法学习与工程开发中，遇到以下关键词时应当高度警惕：

• “求最大值中的最小值”
• “求最小值中的最大值”
• “满足特定限制下的最小代价 / 最短时间”

这类问题如果直接构造最优解，往往涉及复杂的全局状态或组合搜索；但如果我们猜一个答案 $x$，问：“代价不超过 $x$ 时，能否达成目标？”，这个问题往往变得格外容易判定（通常用简单的线性扫描或贪心即可完成）。

单调性是二分的前提

假设可行性判定函数为 $check(x)$： 如果对于所有可能取值，$check(x)$ 的返回值呈现出类似： $\text{False, False, False, }\mathbf{True},\text{True, True}\dots$ 的阶跃单调形态，那么我们就可以利用二分在 $O(\log (\text{range}))$ 次判定内精准锁定这个分界点。

避开边界陷阱的代码规范

二分边界常容易导致死循环。推荐固定的闭区间写法：

long long left = min_val, right = max_val;
long long ans = right;

while (left <= right) {
    long long mid = left + (right - left) / 2;
    if (check(mid)) {
        ans = mid;         // 记录当前可行解
        right = mid - 1;   // 尝试寻找更优的可行解
    } else {
        left = mid + 1;    // 不可行，答案必须更大
    }
}

牢记：先判定，后记录，再收缩。把最优化化归为单调判定，是对复杂问题降维打击的核心思维。