1. 使用场景
二分答案一般使用在求解符合条件的最小值或者最大值上面, 当我们遇到这两个问题的时候, 一般都可以使用二分答案来解决问题.
2. 什么是二分答案
二分答案就是通过对所有可能的答案区间进行折半查找, 不断缩减范围, 最终确定答案的方法.
3. 求最小值
- // 求最小值
- int binary(int left, int right) {
- int mid;
- while(left <right) {
- mid = (right + left) / 2;
- if (check(mid)) right = mid;
- else left = mid + 1;
- }
- return left;
- }
我们可以知道, 要求最小值, 那么所满足条件的值赋值给右边界, 不满足的值加一赋值给左边界, 当 left == right 或者 left> right 时, 则说明已经查询到符合的最小值.
4. 求最大值
- // 求最大值
- int binary(int left, int right) {
- int mid;
- while(left < right) {
- mid = (right + left + 1) / 2;
- if (check(mid)) left = mid;
- else right = mid - 1;
- }
- return left;
- }
同样, 要求最大值, 那么就需要舍弃符合条件的较小的值, 即将左边界赋值符合条件的点, 右边界赋值不符合条件的值减一. 不断查询下去, 则最后剩下符合条件最大值. 其中 mid = (right + left + 1) / 2 是为了防止无限循环, 因为当 left = right + 1 时刚好符合条件, left = (right + left) / 2, 就会无限循环.
5. check 函数构思
我们既然选择了使用二分法来求解, 那么我们在 check 的时候, 应该是在我们已知答案的情况下去确认答案, 即不是从一般思考方向设想, 而是验证. check 函数往往是基于假定知道答案, 来验证是否正确.
[模板] 二分答案
来源: http://www.bubuko.com/infodetail-3383997.html