算法基础算法

实数区间二分

字数统计: 970字   |   阅读时长: 3分
, , ,

摘要: 实数区间二分的场景与代码模板，经典题目 lc69

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在文章 二分 中，我们总结了二分的常见类型，其中主要是区间二分以及值域二分。

本文我们了解一下实数区间二分，首先我们从实数定义域的单根函数求根这个问题引入，给出代码模板。然后我们解决力扣上的经典问题：69。

场景：实数定义域的单根单调函数求根

下图可以直观地看出我们要解决的问题：已知函数 f(x) 在区间 (l, r) 上单调且有一个根，找到这个根。

我们所求的值的取值范围是 (l, r)，这里 l, r 是实数。取 l, r 的中点 mid，看 f(mid) 大于 0 还是小于 0。

  • 如果 f(mid) < 0，由于 f 在 (l, r) 单调递增，因此 (l, mid) 这个范围上 f 也是小于 0 的，这样我们的答案范围就变成了 (mid, r)。
  • 如果 f(mid) > 0，由于 f 在 (l, r) 单调递增，因此 (mid, r) 这个范围上 f 也是大于 0 的，这样我们的答案范围就变成了 (l, mid)。

以上过程类似于区间二分，只是在我们遇到的绝大多数区间二分问题的取值是整数，这里的取值是实数。

代码 (C++) 模板

将以上二分的过程写成代码，如下，这是实数定义域的单根单调函数求根的代码模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const double EPS = 1e-10;
double l = L, r = R;
double zero_point = r;

while(l + EPS < R)
{
    double mid = (l + r) / 2.0;
    if(f(mid) > 0)
    {
        r = mid;
        zero_point = min(zero_point, mid);
    }
    else
        l = mid;
}

题目: x 的平方根

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

提示：

1
0 <= x <= 2^31 - 1

示例 1：
输入：x = 4
输出：2

示例 2：
输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842…, 由于返回类型是整数，小数部分将被舍去。

代码 (C++)

我们要求根的函数是 f(a) = a * a - x，其中 a 的范围是 [0, 2^31-1]。

在 a 的范围中 f(a) 是单调递增的。因此可以用二分的方式求 f(a) 的单根。

直接按照前面的代码模板写即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int mySqrt(int x) {
        if(x == 0) 
            return 0;
        const double EPS = 1e-10;
        double l = 1, r = x;
        double ans = r;
        while(l + EPS < r)
        {
            double mid = (l + r) / 2.0;
            if(mid * mid - x > 0)
            {
                r = mid;
                ans = min(ans, mid);
            }
            else
                l = mid;
        }
        return ans;
    }
};

实数二分答案的取整问题

实数二分的问题，最后答案需要上取整或下取整的时候，需要注意最终的整数答案是 int(left) 还是 int(right)。

当我们用实数二分求一个值的时候，这个值会从上下两个方向趋近于答案，比如答案是 100，而 left 等于 99.99999，right 等于 100.00001，随着精度的提高，这两边会越来越趋近于 100，但是 left 始终比 100 小一点，right 始终比 100 大一点。因此：

  • 向下取整必须用 right 向下取整来得到答案，因为 right 比答案要大一点点。
  • 向上取整必须用 left 向上取整来得到答案，因为 left 比答案要小一点点。
Share