罗罗编程学习记录
本页内容 展开查看

02.5.1.3 二分答案

所属:全栈开发面试题库 / 02 数据结构与算法 / 02.5 二分与排序 / 02.5.1 二分查找

02.5.1.3-001 什么是二分答案?

一句话结论

当候选答案在整数区间上单调可行(答案越大越容易满足,或越小越容易),对答案二分,用 check(x) 判定可行性,收敛到边界值;数组本身不必有序。

概念解释

  • 候选:答案值。
  • 单调可行:可行/不可行分界。
  • 判定函数。

原理流程

  1. 确定答案上下界。
  2. 中点 check。
  3. 按可行方向收缩。

代码 / 图示

不可行 | 可行  → 找最小可行
可行 | 不可行  → 找最大可行

常见误区

  • 误区:二分答案要求输入数组有序;正解:只要求可行性关于答案单调。
  • 误区:check 结果不单调也二分;正解:必须先证明单调性。

追问

  • Q:典型题型? A:最大值最小化、最小值最大化。
  • Q:答案一定是整数吗? A:常见整数;浮点按精度二分。

02.5.1.3-002 最大值最小化与最小值最大化是什么?

一句话结论

最大值最小化:在限制条件下让最大代价尽量小(如分割数组使最大段和最小);最小值最大化:让最小收益尽量大(如分礼物使最小间距最大);两者都二分答案。

概念解释

  • 目标极值。
  • 约束条件。
  • 二分方向。

原理流程

  1. 明确优化目标。
  2. 写可行性判定。
  3. 二分边界值。

代码 / 图示

最大段和最小:二分上限,check 能否分段
最小间距最大:二分间距,check 能否放下

常见误区

  • 误区:两类目标二分方向相同;正解:一个找最小可行,一个找最大可行。
  • 误区:直接 DP 枚举;正解:单调性成立时二分更优。

追问

  • Q:LC 410 属于哪类? A:最大值最小化。
  • Q:LC 475 供暖半径? A:最大值最小化(覆盖半径最小)。

02.5.1.3-003 check 判定函数怎么写?

一句话结论

给定候选答案 x,按题意模拟贪心/计数,判断能否在 x 限制下完成;check 必须正确反映可行性,且结果随 x 单调;通常 O(n) 扫描。

概念解释

  • 模拟判定。
  • 贪心计数。
  • 单调前提。

原理流程

  1. 遍历输入。
  2. 按 x 累计代价/数量。
  3. 返回是否满足限制。

代码 / 示例

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 可行,下界保证不可行或边界。

概念解释

  • 下界:最小候选。
  • 上界:可行基准。
  • 区间覆盖答案。

原理流程

  1. 估算最小可能值。
  2. 取一定可行上界。
  3. 二分收敛。

代码 / 图示

分割数组:下界 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. 下界 1,上界最大堆。
  2. check 累加耗时。
  3. 收缩找最小 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 为元素和。

概念解释

  • 最大段和。
  • 贪心分段。
  • 最小化上限。

原理流程

  1. 下界 max(a),上界 sum(a)。
  2. check 累计段和超 limit 新开段。
  3. 段数 ≤ 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)。

概念解释

  • 顺序不可拆。
  • 载重单调。
  • 最小化载重。

原理流程

  1. 下界 max(weight),上界 sum。
  2. check 顺序累计超重开一天。
  3. 天数 ≤ 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;找最大可行长度。

概念解释

  • 段数随长度递减。
  • 最大可行长度。
  • 整除计数。

原理流程

  1. 下界 0,上界最长木料。
  2. check 累加 ⌊len/x⌋。
  3. 段数 ≥ 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)。

概念解释

  • 覆盖半径。
  • 最近供暖器。
  • 最小化半径。

原理流程

  1. 排序供暖器。
  2. 二分半径。
  3. 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;终点返回边界;先定目标方向再套模板。

概念解释

  • 方向模板。
  • 收缩保留。
  • 终止返回。

原理流程

  1. 判断找最小/最大可行。
  2. 选收缩方向。
  3. 收敛返回。

代码 / 示例

// 最小可行
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,判定代价计入总复杂度。

概念解释

  • 比较对象。
  • 单调来源。
  • 复杂度口径。

原理流程

  1. 数组:元素有序。
  2. 答案:可行性单调。
  3. 判定函数不同。

代码 / 图示

数组: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'(更大上限/更小间距按方向)也可行;证明放宽约束不会破坏可行性;单调是二分答案成立的前提。

概念解释

  • 可行集单调。
  • 放宽约束。
  • 分界唯一。

原理流程

  1. 设 x 可行。
  2. 放宽到 x'。
  3. 同一方案仍满足约束。

代码 / 图示

limit 越大 → 分段越容易

常见误区

  • 误区:不验证单调直接二分;正解:先证明可行集连续单调。
  • 误区:非单调问题硬套二分;正解:结果可能漏解。

追问

  • Q:单调性反方向? A:同理,可行集一侧连续。
  • Q:怎么写证明? A:举方案随约束放宽仍成立。

02.5.1.3-013 check 的贪心为什么通常正确?

一句话结论

可行性判定只需判断“能否完成”,贪心取最省资源方案即可证明是否有可行解;最优解不在 check 内求,而由二分边界给出;贪心失败即不可行。

概念解释

  • 判定非优化。
  • 最省资源。
  • 二分给极值。

原理流程

  1. 贪心尽量省。
  2. 省下来仍超约束即不可行。
  3. 边界值即最优。

代码 / 图示

装船:顺序能省则省,超重才开新段

常见误区

  • 误区:check 内求最优分段;正解:只判可行。
  • 误区:贪心选择影响最优值;正解:二分边界决定。

追问

  • Q:贪心不成立怎么办? A:check 需换正确判定方法。
  • Q:同题 DP 对比? A:DP 求具体方案,二分求边界。

02.5.1.3-014 二分答案有哪些边界用例?

一句话结论

单元素、所有元素相等、k=1、k≥n、答案恰为单元素值、答案为总和、不可行极端值;检查上下界覆盖与 check 边界计数。

概念解释

  • 最短输入。
  • 极端分组。
  • 端点答案。

原理流程

  1. 单元素答案即其值。
  2. k=1 答案总和。
  3. 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 → 方向复核。

概念解释

  • 边界覆盖。
  • 判定正确。
  • 方向口径。

原理流程

  1. 复核上界可行。
  2. 复核 check 计数。
  3. 复核收缩方向。

代码 / 图示

上界可行 → 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 本身带排序另计预处理。

概念解释

  • 轮次对数。
  • 判定代价。
  • 辅助空间。

原理流程

  1. 标注答案范围 R。
  2. 每轮判定复杂度。
  3. 相乘得总时间。

代码 / 图示

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/贪心;满足单调再二分。

概念解释

  • 极值目标。
  • 可行单调。
  • 方案记录需求。

原理流程

  1. 看目标是否数值极值。
  2. 验证可行单调。
  3. 选二分或其他。

代码 / 图示

极值 + 单调可行 → 二分答案
需具体分配 → DP/贪心

常见误区

  • 误区:求最优排列也二分;正解:可行性单调才适用。
  • 误区:check 需复杂优化;正解:那题可能不适合二分答案。

追问

  • Q:最小路径代价? A:图上最短路,非二分答案。
  • Q:第 K 小? A:见堆/快速选择,非二分答案典型。

02.5.1.3-018 浮点二分答案怎么处理?

一句话结论

整数边界二分改为浮点区间,按精度迭代固定轮次或直到区间小于 eps;check 比较带容差;输出保留指定位数;避免死循环。

概念解释

  • 精度 eps。
  • 固定轮次。
  • 容差比较。

原理流程

  1. 浮点上下界。
  2. 迭代固定次数(如 100 轮)。
  3. 输出区间中点。

代码 / 示例

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 对比、单调性怎么证明;回答围绕可行单调与判定代价。

概念解释

  • 前提证明。
  • 边界口径。
  • 复杂度。

原理流程

  1. 说单调性。
  2. 写 check。
  3. 报复杂度。

代码 / 图示

单调 → 上下界 → check → 二分收敛

常见误区

  • 误区:追问复杂度只答 log;正解:乘 check。
  • 误区:说不清上下界来源;正解:按单元素与总和推导。

追问

  • Q:check 失败说明什么? A:当前答案不可行,向可行侧收缩。
  • Q:二分答案能返回方案吗? A:边界值可得,具体分配需另跑贪心。

02.5.1.3-020 二分答案常见变体有哪些?

一句话结论

吃香蕉、分割数组、运包裹、木材切段、供暖半径、最小化最大距离、最大化最小分配、浮点精度问题;主线是可行单调 + check 判定 + 方向模板。

概念解释

  • 框架:二分答案。
  • 变体:判定场景。
  • 方向:最小/最大可行。

原理流程

  1. 定答案值域。
  2. 写 check。
  3. 套方向模板。

代码 / 图示

上限类:最小可行
间距类:最大可行

常见误区

  • 误区:变体题混淆最大/最小方向;正解:先读目标极值。
  • 误区:check 漏边界约束;正解:单元素与满分组自测。

追问

  • Q:最大间距(LC 1552 类)? A:最大化最小值,可行则 l=mid。
  • Q:与排序结合? A:check 常需先排序输入。