leetcode 链接：x 的平方根

题目

实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例：

输入: 4
输出: 2

输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 
     由于返回类型是整数，小数部分将被舍去。

解答 & 代码

解法一：二分查找

class Solution {
public:
    int mySqrt(int x) {
        int left = 0;
        int right = x;
        int result = -1;
        while(left <= right)    // 二分查找
        {
            int mid = left + (right - left) / 2;
            if((long long)mid * mid <= x)    // 注意使用 long long
            {
                result = mid;
                left = mid + 1;
            }
            else
                right = mid - 1;
        }
        return result;
    }
};

执行结果：

执行结果：通过

执行用时：5 ms, 在所有 C++ 提交中击败了 57.87% 的用户
内存消耗：5.9 MB, 在所有 C++ 提交中击败了 8.09% 的用户

解法二：牛顿迭代法

正数 C 的平方根就是函数 的零点

• 取 作为初始值
  • 因为曲线有 两个零点，为了使得最终能迭代到 这个零点，因此取 右边的数 C 作为初始值，保证每次迭代的 都在零点 右侧
• 对于每个 ，其在曲线上的点为 ，以该点导数 为斜率且经过该点的直线为：
• 该直线与横轴的交点
• 进行多次迭代，直至 ， 一般可以取 ，此时的 向下取整即为 x 的平方根

class Solution {
public:
    int mySqrt(int x) {
        if(x == 0)
            return 0;

        double C = x;
        double x0 = C;                                // x_i
        while(true)
        {
            double x1 = 0.5 * (x0 + C / x0);        // x_{i+1}
            if(fabs(x0 - x1) < 1e-7)
                break;
            x0 = x1;
        }
        return int(x0);
    }
};

复杂度分析：

• 时间复杂度 O(log x)
• 空间复杂度 O(1)

执行结果：通过

执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户
内存消耗：5.7 MB, 在所有 C++ 提交中击败了 91.03% 的用户