二分答案与三分法
基于通用算法套路 · 核于 2026-07
速查
- 二分答案核心思想：不再对「下标」二分，而是对「答案值域」
[L, R]二分——每次取候选答案mid，调用check(mid)判定是否可行，靠「可行性关于答案单调」折半值域，最终收敛到最优答案。 - 适用条件（三要素）：①答案有明确上下界（值域有限或可限定）；②
check(x)可在多项式时间完成；③可行性单调——「答案越大越难满足」或「越小越难」（即存在一个临界值，一侧全可行、另一侧全不可行）。 - 模板形态：求「最大化最小值」类，找最大的
x使check(x)为真——check(mid) ? lo = mid : hi = mid - 1（上取整mid）；求「最小化最大值」类，找最小的x使check(x)为真——check(mid) ? hi = mid : lo = mid + 1（下取整mid）。 check的设计是核心：check(x)通常是个贪心或模拟，判断「在答案不超过/不低于x的约束下能否达成目标」。- 复杂度：O(log(值域) × 复杂度(check))。值域越大迭代越多，但 log 增长慢，常可接受。
- 经典题型：「最大化最小值」「最小化最大值」「第 k 小」「可行性判定」——如分裂数组最大值最小化、木头切割得至少 k 段、吃香蕉速度、运送货物天数。
- 三分法（Ternary Search）：当目标函数
f(x)**单峰（先增后减）或单谷（先减后增）**时，取两个内分点m1 = lo + (hi-lo)/3、m2 = hi - (hi-lo)/3，比较f(m1)与f(m2)，每次排除左或右三分之一的区间，逼近极值。 - 三分判定：单峰时
f(m1) < f(m2)⇒ 极值在m1右侧（lo = m1），否则在m2左侧（hi = m2）；单谷时方向相反。 - 三分复杂度：每次区间缩到 2/3，O(log n)（底数 1.5）；浮点场景需设精度
eps或固定迭代次数（如 100 次保证精度）。 - 三分 vs 二分答案：三分要函数凸/凹（单峰/单谷），二分答案要判定单调（一侧可行一侧不可行）；多峰函数三分不适用。
- 易错点：二分答案的
mid取整方向（避免死循环）、check的单调性验证、三分浮点的精度与终止条件。
一、二分答案：对值域二分 + check 验证
朴素二分搜索的是「下标」，二分答案搜索的是「答案」。典型场景：「求满足某条件的最优解」，且可行性关于答案单调。
思想
把「找最优答案」转化为「反复判定一个候选答案可不可行」：
答案轴： L ─────────────── R
↑ mid（候选答案）
check(mid)?
真 → 答案可以更大/更小（往一侧缩）
假 → 答案不可行（往另一侧缩）只要「可行 / 不可行」在答案轴上是连续的单调区间（一侧全可行、一侧全不可行），就能折半。
适用条件（务必先验证）
- 答案有界：能确定答案的最小值
L和最大值R（如「分裂数组最大值」在[max(nums), sum(nums)]之间）。 check多项式可解：给定答案x，能在 O(n) 或 O(n log n) 内判定是否可行。- 可行性单调：这是最关键的前提——若
x可行则所有「更宽松」的答案也可行（或反之）。例如「最大值不超过x」中，x越大约束越宽松越易满足。
模板：求最大的 x 使 check(x) 为真（「最大化最小值」类）
js
// 典型：把数组分成 k 段，使各段和的最大值最小化 → 反过来是「最大的 x 使 check 真」
function binaryAnswerMax(nums, k) {
let lo = Math.max(...nums), hi = nums.reduce((a, b) => a + b); // 答案上下界
while (lo < hi) {
const mid = (lo + hi + 1) >> 1; // 上取整，避免死循环
check(nums, mid, k) ? (lo = mid) : (hi = mid - 1);
}
return lo;
}
// check：限制每段和 ≤ limit 时，至少要分多少段；≤ k 段则可行经典题：木头切割（至少得 k 段）
有 n 根木头，每根长
L[i]，要切成等长x的小段（不计余料），至少得到 k 段。求x的最大值。
check(x)：每根能切 floor(L[i]/x) 段，总和 ≥ k 则可行。x 越大切的段越少——可行性单调（小 x 易可行，大 x 难）。对 x 二分即可。
js
function maxWoodLength(L, k) {
let lo = 1, hi = Math.max(...L);
while (lo < hi) {
const mid = (lo + hi + 1) >> 1; // 上取整
const segs = L.reduce((s, len) => s + Math.floor(len / mid), 0);
segs >= k ? (lo = mid) : (hi = mid - 1);
}
return lo;
}经典题：分裂数组最大值最小化
把数组分成 m 个连续子数组，使各子数组和的最大值最小。
答案在 [max(nums), sum(nums)]。check(limit)：贪心模拟，每段加到不超过 limit 就新开一段，统计段数 ≤ m 则可行。答案越大越易满足——单调，可二分找最小的可行 limit。
js
function splitArray(nums, m) {
let lo = Math.max(...nums), hi = nums.reduce((a, b) => a + b, 0);
while (lo < hi) {
const mid = (lo + hi) >> 1; // 下取整
let cnt = 1, sum = 0;
for (const x of nums) {
if (sum + x > mid) { cnt++; sum = 0; }
sum += x;
}
cnt <= m ? (hi = mid) : (lo = mid + 1); // 段数少说明 limit 够大
}
return lo;
}二、三分法：单峰函数求极值
当目标函数 f(x) 是**单峰（凸，先增后减）或单谷（凹，先减后增）**时，用三分法在连续定义域上找极值。
思想
取两个内分点 m1 < m2，把区间三等分，比较 f(m1) 与 f(m2)：
单峰 f： /\
m1 m2 （极值在中间）
f(m1) < f(m2) → 极值在 m1 右侧 → lo = m1
f(m1) > f(m2) → 极值在 m2 左侧 → hi = m2每次区间缩到 2/3，几何级数收敛，O(log n)（底数 1.5）。
模板（浮点，单峰求最大值）
js
function ternarySearch(f, lo, hi) {
const eps = 1e-8; // 精度
while (hi - lo > eps) {
const m1 = lo + (hi - lo) / 3;
const m2 = hi - (hi - lo) / 3;
f(m1) < f(m2) ? (lo = m1) : (hi = m2); // 单峰：小的一侧排除
}
return (lo + hi) / 2; // 近似极值点
}整数三分（求离散单峰极值下标）：用循环 while (hi - lo > 2)，比较 f(m1) 与 f(m2) 缩区间，最后在剩余 2-3 个点里取极值。
适用前提与陷阱
- 必须严格单峰/单谷：多峰函数三分会收敛到某个局部极值，可能不是全局最优。
- 浮点精度：
eps取题目要求的精度再小 1-2 位；或固定迭代 100-200 次（每次精度约提升 1.5 倍，100 次足够）。 - 离散三分注意终止：区间小于 3 时停止枚举，避免
m1 == m2死循环。
三、二分答案 vs 二分下标 vs 三分
| 维度 | 朴素二分（下标） | 二分答案（值域） | 三分（自变量） |
|---|---|---|---|
| 搜索对象 | 数组下标 | 答案的值 | 函数自变量 |
| 单调性来源 | 数组有序 | 可行性关于答案单调 | 函数单峰/单谷（凸性） |
| 判定 | nums[mid] 与 target | check(mid) | f(m1) 与 f(m2) |
| 目标 | 找定值 | 找最优可行答案 | 找极值 |
| 典型题 | 有序数组查值 | 最大化最小值、第 k 小 | 凸函数求最值 |
四、易错点
mid取整方向：「找最大可行答案」用上取整(lo+hi+1)>>1配lo = mid；「找最小可行答案」用下取整(lo+hi)>>1配hi = mid。配错会死循环。check单调性必须验证：若可行性不单调（如某些双峰分布），二分答案失效。- 三分只适用单峰：多峰要先证明单峰性（如距离函数常是凸的）。
- 浮点三分迭代次数：宁可多迭代（100 次）也别太少导致精度不够。
交互演示
下一步
掌握了三变体后，汇总速查模板、复杂度表与适用场景对比，见参考。