2025年基础算法2——二分

科技前沿 • 2025-02-16 20:05 • 阅读 40

大家好，我是讯享网，很高兴认识大家。

二分

有单调性的情况一定可以二分；但是二分不一定需要单调性。

1、整数二分

在这里插入图片描述
讯享网

有两个整数二分的模板，分别可以找到红色/绿色的那个分界点。

但实际应用时，不需要看着这个图去想我需要用哪个模板。而是下面这个步骤：

写好一个check(mid)的函数，这个check要能保证在mid的左右两边，一半是false一半是true
如果当前check(mid)为真，那我下一步是让left = mid还是让right = mid。这分别就对应两个模板了。
两个模板里一个mid = (l + r + 1) / 2，一个mid = (l + r) / 2。这是为了解决一些特殊的边界情况。你当然可以通过一些精心构造的例子，来仔细看看为什么需要这么写。但在面试或者考试的场景，我会建议你直接按模板来。

虽然提供了两个模板，但它们本质是一样的。实际中我们先写出一个满足要求的check()函数，然后看当check(mid)== true时，我们要做r=mid还是l=mid，这分别对应了两个模板。

显然，对于同一个问题，采用的check()函数不一样，会导致我们套用了不同的模板。但它们的本质是一样的。

/*整数二分代码模板*/ bool check(int x) { 
   /* ... */} // 检查x是否满足某种性质 // 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用; int bsearch_1(int l, int r) { 
    while (l < r) { 
    int mid = l + r >> 1; if (check(mid)) r = mid; // check()判断mid是否满足性质 else l = mid + 1; } return l; } // 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用; int bsearch_2(int l, int r) { 
    while (l < r) { 
    int mid = l + r + 1 >> 1; if (check(mid)) l = mid; // check()判断mid是否满足性质 else r = mid - 1; } return l; }

讯享网

2、浮点数二分

和整数二分不同的是，浮点数二分的mid = (l + r) / 2可以等到精确的mid值，不需要像整数那样一个要+1，一个不要+1。而浮点数二分到理论mid的小区间(mid - δ, mid + δ)即可。

讯享网bool check(double x) { 
   /* ... */} // 检查x是否满足某种性质 double bsearch_3(double l, double r) { 
    const double eps = 1e-6; // eps 表示精度，取决于题目对精度的要求 while (r - l > eps) { 
    double mid = (l + r) / 2; if (check(mid)) r = mid; else l = mid; } return l; }

经典例子，用二分求x的3次方根。因为 $y = x^3$ 是单调的，所以可以二分来找解。

这里需要注意的是，二分的范围[left, right]怎么定：

[0, x]; // x < 0时显然错误 [-x, x]; // 当|x|< 1时就错了 [-MAX, MAX]; // 正确

讯享网int main(){ 
    double x; cin >> x; double MAX = 10000; double l = -MAX, r = MAX; // y = x ^3 是单调的，所以可以二分 double eps = 1e-8; // 比答案要求的有效位数多2位一般不会出错。 while (r - l > eps){ 
    double mid = (l + r) / 2; if (mid * mid * mid >= x) r = mid; else l = mid; } printf("%.6lf\n", l); }

下一讲：基础算法3——高精度加减法

2025年基础算法2——二分

二分

1、整数二分

2、浮点数二分

相关推荐