二分法求平方根

Posted on Edited on In

题目描述
平方根的计算是一个常见的数值计算问题。给定一个非负实数 x，求其平方根，即找到一个数 r，使得 r² = x。本问题要求使用二分法来计算平方根，结果保留6位小数。

输入格式
输入共 1 行，包含一个非负实数 x。

输出格式
输出共 1 行，包含 x 的平方根，结果保留6位小数。

数据范围
0 ≤ x ≤ 10000

输入样例1：

1
2

输出样例1：

1
1.414214

输入样例2：

1
16

输出样例2：

1
4.000000

注意事项

  • 二分法求平方根的基本思想是在一个合理的范围内不断缩小查找区间，直到达到所需的精度。
  • 对于非负实数 x，其平方根的范围是 [0, max(x, 1)]。
  • 需要设置一个精度阈值，当查找区间的长度小于该阈值时，认为已经找到足够精确的结果。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
#include <iomanip>
using namespace std;

// 二分法计算平方根
double sqrtBinarySearch(double x, double precision)
{
    // 处理特殊情况
    if (x == 0 || x == 1)
    {
        return x;
    }
    
    double left, right;
    // 确定查找范围
    if (x < 1)
    {
        left = x;
        right = 1;
    }
    else
    {
        left = 1;
        right = x;
    }
    
    // 二分查找
    while (right - left > precision)
    {
        double mid = left + (right - left) / 2;
        double mid_squared = mid * mid;
        
        if (mid_squared == x)
        {
            return mid; // 找到精确的平方根
        }
        else if (mid_squared < x)
        {
            left = mid; // 在右半部分继续查找
        }
        else
        {
            right = mid; // 在左半部分继续查找
        }
    }
    
    // 返回区间中点作为结果
    return (left + right) / 2;
}

int main()
{
    double x;
    cin >> x;
    
    double precision = 1e-8; // 设置精度阈值（比要求的6位小数更高，以确保结果正确）
    double result = sqrtBinarySearch(x, precision);
    
    // 输出结果，保留6位小数
    cout << fixed << setprecision(6) << result << endl;
    
    return 0;
}

时间复杂度

  • 时间复杂度：O(log(x/precision))，其中 x 是输入的非负实数，precision 是精度阈值。
  • 空间复杂度：O(1)。

代码解释

  • 二分法求平方根的核心思想是在一个合理的范围内不断缩小查找区间，直到达到所需的精度。
  • 对于非负实数 x，我们需要确定一个合理的查找范围：
    • 如果 x < 1，那么平方根的范围是 [x, 1]。
    • 如果 x ≥ 1，那么平方根的范围是 [1, x]。
  • 在每次迭代中，我们计算区间中点 mid，并计算 mid²。然后根据 mid² 与 x 的大小关系，调整查找区间：
    • 如果 mid² < x，说明平方根在 [mid, right] 范围内。
    • 如果 mid² > x，说明平方根在 [left, mid] 范围内。
  • 重复上述过程，直到查找区间的长度小于设定的精度阈值。
  • 最后，返回区间中点作为平方根的近似值。