题解 | #平方根#

题目链接

平方根

题目描述

这是一个函数实现题。你需要实现一个 findSqrt 函数，它接受一个非负整数 n作为参数，计算 n 的平方根，并返回一个 double（或 float）类型的浮点数结果。

精度要求：只要你的返回值与真实平方根的绝对误差在 $10^{-7}$ 以内，答案即被视为正确。

平台工作模式:

你只需要在给定的函数框架内编写核心逻辑。
评测系统会自动调用你的函数并验证结果。
你不应该编写 main 函数或任何输入/输出代码。

示例:

输入: 2 (由平台处理)
你的函数被调用: findSqrt(2)
你的函数应返回: 1.41421356...

解题思路

这道题要求计算一个非负整数的精确浮点数平方根。

思路一：使用内置函数 (推荐)

这是最简单、最直接、也是在实际工程和大多数编程竞赛中最常用的方法。几乎所有主流编程语言都在其数学库中提供了计算平方根的函数。

C++: 在 <cmath> 头文件中，sqrt() 函数可以计算一个 double 类型数字的平方根。
Java: Math 类提供了 sqrt() 方法。
Python: math 模块提供了 sqrt() 函数。

我们只需要将输入的整数 n 传递给这个函数，然后返回其结果即可。这是解决此问题的最佳实践，代码简洁且不会有精度问题。

思路二：二分查找法

如果我们不能使用内置函数，或者想展示对数值计算算法的理解，二分查找是一个经典且有效的算法。

其基本思想是：对于给定的数 n，它的平方根 x 肯定在 0 到 n 的区间内（当 n>=1 时）。我们可以在这个区间内通过二分法来不断逼近真实的平方根。

确定搜索区间: 初始化 low = 0.0。对于 high，可以直接设为 n（或 (double)n）。
循环逼近: 进行足够多次循环（例如100次，对于 double 精度绰绰有余），或者直到 high - low 小于题目要求的精度 $10^{-7}$ 。
取中点: 在每次循环中，计算中间值 mid = low + (high - low) / 2。
收缩区间:
- 如果 mid * mid > n，说明 mid 比真实平方根大，那么真正的平方根应该在 [low, mid] 区间内。因此，我们令 high = mid。
- 如果 mid * mid <= n，说明 mid 比真实平方根小或等于，那么真正的平方根应该在 [mid, high] 区间内。因此，我们令 low = mid。
返回结果: 循环结束后，low (或 high) 的值就是我们所求的、满足精度要求的平方根。

虽然代码更长，但这个方法体现了非常重要的数值逼近思想。对于本题，使用思路一即可。

代码

注意：以下是你需要提交的全部内容，即在牛客网给定的模板中填写的代码。

c++
java
python

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求非负整数 n 的平方根
     * @param n int整型 你需要求 n 的平方根
     * @return double浮点型
     */
    double findSqrt(int n) {
        // write code here
        // 直接调用标准库的 sqrt 函数
        return sqrt((double)n);
    }
};

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求非负整数 n 的平方根
     * @param n int整型 你需要求 n 的平方根
     * @return double浮点型
     */
    public double findSqrt (int n) {
        // write code here
        // 直接调用 Math 类的 sqrt 方法
        return Math.sqrt(n);
    }
}

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 求非负整数 n 的平方根
# @param n int整型 你需要求 n 的平方根
# @return double浮点型
#
import math
class Solution:
    def findSqrt(self , n: int) -> float:
        # write code here
        # 直接调用 math 模块的 sqrt 函数
        return math.sqrt(n)

算法及复杂度

算法: （内置函数）/ 数值逼近。
时间复杂度: $\mathcal{O}(1)$ 。内置的 sqrt 函数通常由硬件指令（如 FSQRT）实现，速度极快，可视为常数时间。如果使用二分法，其时间复杂度为 $\mathcal{O}(\log(\frac{N}{\epsilon}))$ ，其中 N 是数字大小，epsilon 是精度，对于固定精度，也可以看作是常数时间。
空间复杂度: $\mathcal{O}(1)$ 。没有使用额外的、与输入规模相关的存储空间。