---

---

69. x 的平方根：

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

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

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

样例 1：

输入：
	
	x = 4
	
输出：
	
	2

样例 2：

输入：
	
	x = 8
	
输出：
	
	2
	
解释：
	
	8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

提示：

• 0 31 – 1

---

分析：

• 面对这道算法题目，二当家的再次陷入了沉思。
• 要开平方，但是不允许使用内置的指数函数，这是故意难为我胖虎。
• 暴力破解，反正只要整数，从 1 到 x ，一个一个试，就能找到最接近的解，很简单，但是过于简单了，一定还有更好的办法。
• 答案只要整数，从线性连续的数值里找最优，想到可以用二分查找法，不断尝试，二分查找的效率很高，每次都能减少一半的数据量，已经可以满意了。
• 还有一个更好的办法，答案要的是近似的整数，所以还可以使用 牛顿迭代法 ，非常适合高效找到近似解，听说效率比二分查找还高。
• 感觉数学还是厉害啊，很多东西都是可以用数学的方法高效解决的，虽然计算机已经很快了，但是很多时候用数学的方式去解决，可以快上加快，很想学好数学。
• 下面的题解都是使用 牛顿迭代法，找近似解，所以需要有个度，一个停止继续的点，一般认为两次连续求得的解的差非常小的时候，就是应该停止继续循环的时候，我们这里使用 e^-7 作为两次求解的检查。

---

题解：

rust：

impl Solution {
    pub fn my_sqrt(x: i32) -> i32 {
        if x == 0 {
            return 0;
        }

        let (c, mut x0) = (x as f64, x as f64);
        loop {
            let xi = 0.5 * (x0 + c / x0);
            if (x0 - xi).abs()  1e-7 {
                break;
            }
            x0 = xi;
        }

        return x0 as i32;
    }
}

---

go：

func mySqrt(x int) int {
    if x == 0 {
		return 0
	}

	c, x0 := float64(x), float64(x)
	for {
		xi := 0.5 * (x0 + c/x0)
		if math.Abs(x0-xi)  1e-7 {
			break
		}
		x0 = xi
	}

	return int(x0)
}

---

c++：

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

        double c = x, x0 = x;
        while (true) {
            double xi = 0.5 * (x0 + c / x0);
            if (fabs(x0 - xi)  1e-7) {
                break;
            }
            x0 = xi;
        }

        return int(x0);
    }
};

---

python：

class Solution:
    def mySqrt(self, x: int) -> int:
        if x == 0:
            return 0

        c, x0 = float(x), float(x)
        while True:
            xi = 0.5 * (x0 + c / x0)
            if abs(x0 - xi)  1e-7:
                break
            x0 = xi

        return int(x0)

---

java：

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

        double c = x, x0 = x;
        while (true) {
            double xi = 0.5 * (x0 + c / x0);
            if (Math.abs(x0 - xi)  1e-7) {
                break;
            }
            x0 = xi;
        }

        return (int) x0;
    }
}

---

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】三连走一波~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://le-yi.blog.csdn.net/ 博客原创~

---