02.5.1.3 二分答案
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.5 二分与排序 / 02.5.1 二分查找
02.5.1.3-001 什么是二分答案?
一句话结论
当候选答案在整数区间上单调可行(答案越大越容易满足,或越小越容易),对答案二分,用 check(x) 判定可行性,收敛到边界值;数组本身不必有序。
概念解释
- 候选:答案值。
- 单调可行:可行/不可行分界。
- 判定函数。
原理流程
- 确定答案上下界。
- 中点 check。
- 按可行方向收缩。
代码 / 图示
不可行 | 可行 → 找最小可行
可行 | 不可行 → 找最大可行
常见误区
- 误区:二分答案要求输入数组有序;正解:只要求可行性关于答案单调。
- 误区:check 结果不单调也二分;正解:必须先证明单调性。
追问
- Q:典型题型? A:最大值最小化、最小值最大化。
- Q:答案一定是整数吗? A:常见整数;浮点按精度二分。
02.5.1.3-002 最大值最小化与最小值最大化是什么?
一句话结论
最大值最小化:在限制条件下让最大代价尽量小(如分割数组使最大段和最小);最小值最大化:让最小收益尽量大(如分礼物使最小间距最大);两者都二分答案。
概念解释
- 目标极值。
- 约束条件。
- 二分方向。
原理流程
- 明确优化目标。
- 写可行性判定。
- 二分边界值。
代码 / 图示
最大段和最小:二分上限,check 能否分段
最小间距最大:二分间距,check 能否放下
常见误区
- 误区:两类目标二分方向相同;正解:一个找最小可行,一个找最大可行。
- 误区:直接 DP 枚举;正解:单调性成立时二分更优。
追问
- Q:LC 410 属于哪类? A:最大值最小化。
- Q:LC 475 供暖半径? A:最大值最小化(覆盖半径最小)。
02.5.1.3-003 check 判定函数怎么写?
一句话结论
给定候选答案 x,按题意模拟贪心/计数,判断能否在 x 限制下完成;check 必须正确反映可行性,且结果随 x 单调;通常 O(n) 扫描。
概念解释
- 模拟判定。
- 贪心计数。
- 单调前提。
原理流程
- 遍历输入。
- 按 x 累计代价/数量。
- 返回是否满足限制。
代码 / 示例
boolean check(int[] a, int limit, int k) {
int groups = 1, sum = 0;
for (int x : a) {
if (sum + x > limit) { groups++; sum = x; }
else sum += x;
}
return groups <= k;
}
常见误区
- 误区:check 用最优算法而非贪心;正解:单调性问题常贪心即可判定。
- 误区:check 边界代价算错;正解:单元素超过 limit 需在上下界排除。
追问
- Q:check 可以 O(log n) 吗? A:可以,整体乘对应复杂度。
- Q:check 不单调怎么办? A:不能二分答案。
02.5.1.3-004 答案上下界怎么确定?
一句话结论
下界取不可能再小的基准(如单元素值、0),上界取一定可行的最大值(如全部元素之和、最大值上限);上界必须保证 check 可行,下界保证不可行或边界。
概念解释
- 下界:最小候选。
- 上界:可行基准。
- 区间覆盖答案。
原理流程
- 估算最小可能值。
- 取一定可行上界。
- 二分收敛。
代码 / 图示
分割数组:下界 max(a),上界 sum(a)
常见误区
- 误区:上界不可行导致二分无答案;正解:上界取总和等确定可行值。
- 误区:下界小于单元素;正解:单元素本身是下限约束。
追问
- Q:答案可能为 0? A:按题意设下界 0。
- Q:上界过大? A:增大 log 轮次,不影响正确性。
02.5.1.3-005 爱吃香蕉的珂珂(LC 875)怎么做?
一句话结论
速度 k 越大吃完越快,可行性单调;二分 k:check 按每堆 ⌈piles[i]/k⌉ 累加小时数,判断是否 ≤ H;找最小可行速度;O(n log M),M 为最大堆量。
概念解释
- 速度单调。
- 向上取整小时。
- 最小可行速度。
原理流程
- 下界 1,上界最大堆。
- check 累加耗时。
- 收缩找最小 k。
代码 / 示例
public int minEatingSpeed(int[] piles, int h) {
int l = 1, r = 0;
for (int p : piles) r = Math.max(r, p);
while (l < r) {
int mid = l + (r - l) / 2;
long hours = 0;
for (int p : piles) hours += (p + mid - 1) / mid;
if (hours <= h) r = mid;
else l = mid + 1;
}
return l;
}
常见误区
- 误区:整数除法未向上取整;正解:
(p+mid-1)/mid。 - 误区:小时数 int 溢出;正解:用 long 累加。
追问
- Q:速度上界? A:最大堆量,超过无意义。
- Q:每小时只吃一堆? A:题意如此,跨堆不补时。
02.5.1.3-006 分割数组最大值(LC 410)怎么做?
一句话结论
把数组分成至多 k 段,使最大段和最小;二分段和上限 limit,check 贪心分段数 ≤ k;找最小可行 limit;O(n log S),S 为元素和。
概念解释
- 最大段和。
- 贪心分段。
- 最小化上限。
原理流程
- 下界 max(a),上界 sum(a)。
- check 累计段和超 limit 新开段。
- 段数 ≤ k 可行。
代码 / 示例
public int splitArray(int[] a, int k) {
long l = 0, r = 0;
for (int x : a) { l = Math.max(l, x); r += x; }
while (l < r) {
long mid = l + (r - l) / 2;
if (check(a, mid) <= k) r = mid;
else l = mid + 1;
}
return (int) l;
}
private int check(int[] a, long limit) {
int groups = 1; long sum = 0;
for (int x : a) {
if (sum + x > limit) { groups++; sum = x; }
else sum += x;
}
return groups;
}
常见误区
- 误区:下界取 0;正解:单元素不超过 limit,下界 max(a)。
- 误区:分段数等于 k 才算可行;正解:≤ k 即可,可再分细。
追问
- Q:DP 解法? A:O(n²k),二分贪心更优。
- Q:元素为负? A:分段贪心口径需调整。
02.5.1.3-007 运送包裹(LC 1011)怎么做?
一句话结论
按顺序装船,船载重量 limit 越大所需天数越少;二分载重,check 顺序贪心装船天数 ≤ D;找最小可行载重;O(n log W)。
概念解释
- 顺序不可拆。
- 载重单调。
- 最小化载重。
原理流程
- 下界 max(weight),上界 sum。
- check 顺序累计超重开一天。
- 天数 ≤ D 可行。
代码 / 示例
public int shipWithinDays(int[] w, int days) {
int l = 0, r = 0;
for (int x : w) { l = Math.max(l, x); r += x; }
while (l < r) {
int mid = l + (r - l) / 2;
if (canShip(w, mid, days)) r = mid;
else l = mid + 1;
}
return l;
}
private boolean canShip(int[] w, int cap, int days) {
int d = 1, cur = 0;
for (int x : w) {
if (cur + x > cap) { d++; cur = x; }
else cur += x;
}
return d <= days;
}
常见误区
- 误区:包裹可拆分装船;正解:按题意不可拆。
- 误区:下界 0;正解:单件重量即下限。
追问
- Q:与 LC 410 区别? A:一个分段数固定,一个天数固定,模型同构。
- Q:顺序能打乱吗? A:不能,贪心按原序。
02.5.1.3-008 木材切分(K 段等长)怎么做?
一句话结论
给定若干木料长度,求能切出 K 段等长木条的最大长度;长度越大段数越少,单调;二分长度,check 累计可切段数 ≥ K;找最大可行长度。
概念解释
- 段数随长度递减。
- 最大可行长度。
- 整除计数。
原理流程
- 下界 0,上界最长木料。
- check 累加
⌊len/x⌋。 - 段数 ≥ K 则尝试更长。
代码 / 图示
长度 x → 段数 Σ floor(len_i / x)
常见误区
- 误区:长度越小越容易满足却找最大;正解:目标是最长可行。
- 误区:整除用小数;正解:整数段数向下取整。
追问
- Q:LC 1891 类似? A:路线杆长,同模型。
- Q:浮点长度? A:按精度二分或转整数倍。
02.5.1.3-009 供暖器半径(LC 475)怎么做?
一句话结论
每个房屋由最近供暖器覆盖;半径越大覆盖越好;二分半径 r,check 每个房屋在某供暖器 r 范围内;找最小可行半径;也可双指针 O(n log n)。
概念解释
- 覆盖半径。
- 最近供暖器。
- 最小化半径。
原理流程
- 排序供暖器。
- 二分半径。
- check 房屋可达性。
代码 / 图示
house h:存在 heater 满足 |h-heater| ≤ r
常见误区
- 误区:按房屋平均分配供暖器;正解:每个房屋找最近。
- 误区:check 未排序加热器;正解:可二分定位最近。
追问
- Q:双指针做法? A:双序列排序后同向扫描最近距离。
- Q:半径上界? A:首尾跨度。
02.5.1.3-010 最小化最大值/最大化最小值模板怎么写?
一句话结论
最小可行值:check(mid) 可行则 r=mid,否则 l=mid+1;最大可行值:可行则 l=mid,否则 r=mid-1;终点返回边界;先定目标方向再套模板。
概念解释
- 方向模板。
- 收缩保留。
- 终止返回。
原理流程
- 判断找最小/最大可行。
- 选收缩方向。
- 收敛返回。
代码 / 示例
// 最小可行
while (l < r) { mid = ...; if (check(mid)) r = mid; else l = mid + 1; }
// 最大可行
while (l < r) { mid = ...; if (check(mid)) l = mid; else r = mid - 1; }
常见误区
- 误区:两类方向混写;正解:先确认目标极值方向。
- 误区:最大可行用
r=mid;正解:可行保留在l=mid。
追问
- Q:
mid偏左影响哪个方向? A:最大可行需配合r=mid-1防卡死。 - Q:答案不存在? A:上界保证可行。
02.5.1.3-011 二分答案与数组二分有什么区别?
一句话结论
数组二分对元素值比较,输入有序;二分答案对可行性判定比较,答案区间单调,输入本身可无序;轮次取决于答案范围 R,判定代价计入总复杂度。
概念解释
- 比较对象。
- 单调来源。
- 复杂度口径。
原理流程
- 数组:元素有序。
- 答案:可行性单调。
- 判定函数不同。
代码 / 图示
数组:a[mid] vs target
答案:check(mid) 可行与否
常见误区
- 误区:二分答案要求数组有序;正解:只要求可行单调。
- 误区:复杂度只报 log R;正解:乘 check 代价。
追问
- Q:check 是 O(n)? A:总 O(n log R)。
- Q:答案范围 R? A:整数上下界差。
02.5.1.3-012 可行性单调性怎么证明?
一句话结论
若答案 x 可行,则任何更宽松的 x'(更大上限/更小间距按方向)也可行;证明放宽约束不会破坏可行性;单调是二分答案成立的前提。
概念解释
- 可行集单调。
- 放宽约束。
- 分界唯一。
原理流程
- 设 x 可行。
- 放宽到 x'。
- 同一方案仍满足约束。
代码 / 图示
limit 越大 → 分段越容易
常见误区
- 误区:不验证单调直接二分;正解:先证明可行集连续单调。
- 误区:非单调问题硬套二分;正解:结果可能漏解。
追问
- Q:单调性反方向? A:同理,可行集一侧连续。
- Q:怎么写证明? A:举方案随约束放宽仍成立。
02.5.1.3-013 check 的贪心为什么通常正确?
一句话结论
可行性判定只需判断“能否完成”,贪心取最省资源方案即可证明是否有可行解;最优解不在 check 内求,而由二分边界给出;贪心失败即不可行。
概念解释
- 判定非优化。
- 最省资源。
- 二分给极值。
原理流程
- 贪心尽量省。
- 省下来仍超约束即不可行。
- 边界值即最优。
代码 / 图示
装船:顺序能省则省,超重才开新段
常见误区
- 误区:check 内求最优分段;正解:只判可行。
- 误区:贪心选择影响最优值;正解:二分边界决定。
追问
- Q:贪心不成立怎么办? A:check 需换正确判定方法。
- Q:同题 DP 对比? A:DP 求具体方案,二分求边界。
02.5.1.3-014 二分答案有哪些边界用例?
一句话结论
单元素、所有元素相等、k=1、k≥n、答案恰为单元素值、答案为总和、不可行极端值;检查上下界覆盖与 check 边界计数。
概念解释
- 最短输入。
- 极端分组。
- 端点答案。
原理流程
- 单元素答案即其值。
- k=1 答案总和。
- k≥n 答案 max。
代码 / 图示
k=1 → sum
k≥n → max
常见误区
- 误区:下界取 0 导致 check 单元素不可行;正解:下界 max。
- 误区:分组数边界 = k 写成 < k;正解:≤ k 可行。
追问
- Q:答案为 0 情形? A:题意允许时下界 0。
- Q:空输入? A:按题意返回 0。
02.5.1.3-015 二分答案常见错误有哪些?
一句话结论
上下界不覆盖答案、check 贪心错误、方向模板写反、计数单位错(向上/向下取整)、溢出未用 long、未证明单调性;按上下界 → check → 方向复核。
概念解释
- 边界覆盖。
- 判定正确。
- 方向口径。
原理流程
- 复核上界可行。
- 复核 check 计数。
- 复核收缩方向。
代码 / 图示
上界可行 → check 正确 → 方向匹配目标
常见误区
- 误区:段数/天数口径写成严格不等;正解:≤ 约束。
- 误区:mid 计算溢出;正解:差值折半或 long。
追问
- Q:check 返回 boolean vs 计数? A:计数便于比较分组数。
- Q:边界值漏判? A:用端点样例验证。
02.5.1.3-016 二分答案复杂度怎么算?
一句话结论
答案区间 [L,R] 二分 O(log(R-L+1)) 轮;每轮 check O(n)(或 O(k)),总 O(n log R);空间 O(1);若 check 本身带排序另计预处理。
概念解释
- 轮次对数。
- 判定代价。
- 辅助空间。
原理流程
- 标注答案范围 R。
- 每轮判定复杂度。
- 相乘得总时间。
代码 / 图示
check O(n):O(n log R)
check O(log n):O(n? 按实际)
常见误区
- 误区:二分答案 O(log n);正解:乘 check 代价。
- 误区:R 用元素个数而非答案范围;正解:轮次由答案值域决定。
追问
- Q:check O(n log n)? A:总 O(n log n log R)。
- Q:空间优化? A:原地扫描 O(1)。
02.5.1.3-017 怎么判断一道题该不该用二分答案?
一句话结论
目标是某个数值的极值(最小化上限/最大化下限),且该值变化时可行性单调;若方案本身可枚举或需记录具体分配,优先 DP/贪心;满足单调再二分。
概念解释
- 极值目标。
- 可行单调。
- 方案记录需求。
原理流程
- 看目标是否数值极值。
- 验证可行单调。
- 选二分或其他。
代码 / 图示
极值 + 单调可行 → 二分答案
需具体分配 → DP/贪心
常见误区
- 误区:求最优排列也二分;正解:可行性单调才适用。
- 误区:check 需复杂优化;正解:那题可能不适合二分答案。
追问
- Q:最小路径代价? A:图上最短路,非二分答案。
- Q:第 K 小? A:见堆/快速选择,非二分答案典型。
02.5.1.3-018 浮点二分答案怎么处理?
一句话结论
整数边界二分改为浮点区间,按精度迭代固定轮次或直到区间小于 eps;check 比较带容差;输出保留指定位数;避免死循环。
概念解释
- 精度 eps。
- 固定轮次。
- 容差比较。
原理流程
- 浮点上下界。
- 迭代固定次数(如 100 轮)。
- 输出区间中点。
代码 / 示例
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;
}
常见误区
- 误区:浮点
l < r死循环;正解:固定轮次或 eps。 - 误区:比较无容差;正解:浮点误差留余量。
追问
- Q:多少轮够精度? A:区间缩小到 1e-7 量级约 50~100 轮。
- Q:整数答案优先? A:能转整数倍就转整数二分。
02.5.1.3-019 二分答案常见追问有哪些?
一句话结论
为什么可行、上下界取多少、check 贪心是否正确、复杂度多少、最坏退化、与 DP 对比、单调性怎么证明;回答围绕可行单调与判定代价。
概念解释
- 前提证明。
- 边界口径。
- 复杂度。
原理流程
- 说单调性。
- 写 check。
- 报复杂度。
代码 / 图示
单调 → 上下界 → check → 二分收敛
常见误区
- 误区:追问复杂度只答 log;正解:乘 check。
- 误区:说不清上下界来源;正解:按单元素与总和推导。
追问
- Q:check 失败说明什么? A:当前答案不可行,向可行侧收缩。
- Q:二分答案能返回方案吗? A:边界值可得,具体分配需另跑贪心。
02.5.1.3-020 二分答案常见变体有哪些?
一句话结论
吃香蕉、分割数组、运包裹、木材切段、供暖半径、最小化最大距离、最大化最小分配、浮点精度问题;主线是可行单调 + check 判定 + 方向模板。
概念解释
- 框架:二分答案。
- 变体:判定场景。
- 方向:最小/最大可行。
原理流程
- 定答案值域。
- 写 check。
- 套方向模板。
代码 / 图示
上限类:最小可行
间距类:最大可行
常见误区
- 误区:变体题混淆最大/最小方向;正解:先读目标极值。
- 误区:check 漏边界约束;正解:单元素与满分组自测。
追问
- Q:最大间距(LC 1552 类)? A:最大化最小值,可行则
l=mid。 - Q:与排序结合? A:check 常需先排序输入。