实现 double sqrt(double x) 并且 x >= 0。

计算并返回 x 开根后的值。

在线评测地址：LintCode 领扣

例 1:

输入: n = 2  输出: 1.41421356 

例 2:

输入: n = 3 输出: 1.73205081 

[题解]

算法：二分

此题有两种做法，一种是牛顿迭代法，一种是二分，这里介绍二分法

• 二分浮点数与寻常二分不同的是while中变成了whlie(left+eps<right)
• 注意小数情况，若x<1将右边界扩大到1可避免结果错误（比如0.04=0.2*0.2）如果我们不将x右边界扩大到1，则无法在[0,0.04]的区间范围内找到正解

复杂度分析

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

• 二分的复杂度

• 空间复杂度O(1)

• 无需额外空间

public class Solution {     /**      * @param x: a double      * @return: the square root of x      */     public double sqrt(double x) {         double left = 0,right = x,mid;         if (right < 1) {             right = 1;         }         while (left + 1e-12 < right) {             mid = left + (right - left) / 2;             if (mid * mid < x) {                 left = mid;             }             else{                 right = mid;             }         }         return left;     } } 

更多题解参见：九章算法

大佬有話說 (0)