二分答案

概念讲解

什么是二分答案？

当答案具有单调性时，可以二分答案，将最优化问题转化为判定问题。

适用场景

  • 最小值最大
  • 最大值最小
  • 第 k 大/小

整数二分

模板

1234567891011121314bool check(int mid) {
    // 判断 mid 是否可行
}

int left = minVal, right = maxVal;
while (left < right) {
    int mid = left + (right - left) / 2;
    if (check(mid)) {
        right = mid;
    } else {
        left = mid + 1;
    }
}
// left 是最小可行解

实数二分

123456789double left = 0, right = 1e9;
while (right - left > 1e-9) {
    double mid = (left + right) / 2;
    if (check(mid)) {
        right = mid;
    } else {
        left = mid;
    }
}

考点分析

初赛考查方式

  1. 程序阅读： 二分答案
  2. 编程题： 最优化问题

常见考点

  • 二分答案模板
  • check 函数设计
  • 单调性判断

例题精讲

例题 1：最小值最大

题目： 将数组分成 m 段，使每段和的最大值最小。

解答：

二分答案 x，check：能否将数组分成 m 段，每段和 ≤ x。

练习题

  1. 二分答案的条件是什么？
查看答案

二分答案的条件：

  1. 答案具有单调性：如果 x 可行，那么所有 ≥ x（或 ≤ x）的值都可行
  2. 可以设计 check 函数：能够判断某个值是否可行

常见场景：

  • 最小值最大化
  • 最大值最小化
  • 第 k 大/小
  1. 如何设计 check 函数？
查看答案

check 函数的设计：

  1. 理解问题：明确要判断什么
  2. 贪心/模拟：用贪心或模拟的方法判断 mid 是否可行
  3. 返回结果：返回 true 或 false

例如：将数组分成 m 段，每段和 ≤ mid

  • 贪心地累加，超过 mid 就分一段
  • 最后看是否 ≤ m 段
  1. 整数二分和实数二分的区别？
查看答案
特性 整数二分 实数二分
范围 整数 实数
终止条件 left < right right - left > eps
精度 精确 可控
时间复杂度 O(log⁡n)O(\log n) O(log⁡(n/eps))O(\log(n/eps))

易错点

⚠️ 注意：

  1. 答案必须有单调性
  2. check 函数要正确
  3. 整数二分注意边界
  4. 实数二分注意精度