69. x的平方根

描述

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

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

示例 1:

输入: 4
输出: 2

示例 2:

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

来源：力扣（LeetCode）
链接：

解题思路

本题解法也是多种多样，本文也是主要介绍常见的两种解法，其它的解法可以参阅John H. Mathews的教案。

求$\sqrt{x}$，等价于求函数$f(a)=a^2-x$的非负解，而求解 方程近似根的方法中，最直观、最简单的方法是二分法，主要思路如下：

• 先找出一个区间[p, q]，使得$f(p)$和 $f(q)$异号
• 求该区间的中点 $m = p + \frac{q - p}{2}$，并求出 $f(m)$ 的值
• 如果$f(m)>0$，即，则取[p, m]为新的区间，否则取[m, q]
• 重复以上两步直到$p >= q$，返回q - 1

具体代码见解法一。

第二种解法为大名鼎鼎的牛顿法，是迭代法的一种，对于二次方根的求解特别有效。

牛顿法具有明显的几何意义，在迭代过程中，以直线代替曲线，用一阶泰勒展式（即在当前点的切线）代替原曲线，求直线与 $x$ 轴的交点，重复这个过程直到收敛。下面这个动图很好地解释了整个过程：

牛顿法的迭代公式如下：

$$a_{n+1}=a_n-\frac{f(a_n)}{f'(a_k)}=a_n-\frac{a_n^2-x}{2a_n}=\frac{a+\frac{x}{a} }{2}$$

知道了原理编码就相当简单了，具体代码见解法二。

代码

解法一

int mySqrt(int x)
{
    long left  = 0, right = x;
    
    if(x <= 1) return x;
    
    else
    {
        while(left < right)
        {
            long mid = left + (right - left)  / 2;
            
            if(mid * mid > x)
                right = mid;
            else
                left = mid + 1;
        }
        
        return (int) (right - 1);
    }
    
}

解法二

int mySqrt(int x)
{
    if(x == 0) return x;
    long result = x;
    while (result * result > x)
    {
        result = (result + x / result) / 2;
    }
    
    return result;
}

参考

• 如何通俗易懂地讲解牛顿迭代法求开方？数值分析？

• Newton’s method

• John H. Mathews的教案