x 的平方根

WangScaler: 一个用心创作的作者。

声明：才疏学浅，如有错误，恳请指正。

题目

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

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

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

初步分析

既然取根号取不了，那么我们反过来想，求平方是否可行呢？求平方的话，我们让两个数相乘，得到的结果如果和我们的目标值距离最近的一个数那么就是目标值的算数平方。

上一篇文章二进制求和我们说过字符串超过 33 位，不能转化为 Integer。我们知道我们int的范围是− 2^31 -2^31-1也就是最大为2147483647。那么我们计算的数如果大于16453的话，两个数相乘就会溢出。所以我们用这个方法的话，得使用long类型，而不能使用int。

继续分析

那么剩下的就是怎么找这个数。我们总不能，从0遍历到最后，他的最大值一定不会大于等于他的一半。例如9/2=4，而4的平方已经是16了，所以他的答案一定在前一半中。从一半这个词，我们想到了二分查找，使用二分查找，就减少了我们一半的遍历。如果使用二分查找的话，初步分析就没什么用了，也就多计算一次的问题。

答案

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

复杂度

• 时间复杂度：O(logn)，二分查找。
• 空间复杂度：O(1),我们只需要几个变量记录我们的数据，左右指针以及中间指针。

总结

看了看答案还有另外一种解法，我们知道平方根反过来想是平方。那么不反过来，而是把平方根的公式转换下呢？

那么也可以调用Math的函数来解决这个问题。还有一个牛顿迭代，比较复杂，数学好的感兴趣的先去看看，我有空了再去研究研究。

都来了，点个赞再走呗！

关注WangScaler，祝你升职、加薪、不提桶！