【经典面试题三】x的平方根的两个解法（二分法，牛顿迭代）

男娘i 2022-09-12 02:56 189阅读 0赞

## 题目 ##

**在不使用sqrt(x)函数的情况下，得到x的平方根的整数部分**

> 例1：  
> 输入：24  
> 输出：4
> 
> 例2：  
> 输入：25  
> 输出：5

相信大家对题目的要求和描述都能了解，那我们直接上解法

#### 解法1：二分查找 ####

**思路**  
x的`平方根的整数部分肯定是在0~x之间`的，所以我们可以直接将其`转换为在以0开头的有序数组中使用二分查找`定位该数字（这数值就是mid:每次二分查找的中间值），那么mid^2一定是最接近x的。

**需要定义的变量**  
l ：表示左边值  
r：表示右边值  
n：表示最终的返回值  
mid：临时存储 l+r 的中间值

**n值的临界条件判断**  
当mid \* mid > x，则 mid 取 l 到 mid -1的中间数，继续循环，直到mid \* mid < x,mid就是要找的数 ；  
当mid \* mid <= x ,则mid取 mid +1 到 r 的中间数，并将mid 赋值给n ，直到两边界限重合，n就是要找的数。

**时间复杂度：O(logN)**

**劣势：当数值大于等于100000时，mid\*mid就会出现数值过大而计算出错**

代码实现如下：

public static int binarySearch(int x){
        
       //l:左边界值;r:右边界值;n:x平方根的最大整数
       int l = 0,r = x,n = -1;
       while (l <= r){
        
           //mid:临时存储中间值
           int mid = (l + r) / 2;
           if (mid * mid <= x) {
        
               n = mid;
               l = mid + 1;
           }else {
        
               r = mid - 1;
           }
       }
       return n;
    }

#### 解法2：牛顿迭代 ####

这种解法是在高数的微积分中推出的，这里我们就不做具体的解释，说一下大概内容：  
求x的平方根，则得到n^2 = x，这是一个抛物线，做抛物线的切线在抛物线上有个切点，有切点就会有斜率，而x的平方根就可以根据切线的不断变化，最终趋近于平方根的解。

**解决这道题的原理：**  
假设`平方根是n`,那么`n 与x / n都是x的因子`，而 `x / n必然等于n`(因为x /n与n都是x的因子，所以只有`当x/n = n时才存在因子的平方等于x`),由此金额`推导出n + x/n = 2*n;所以n = （n + x/n）/ 2`

上述的公式即为其解法，n可选0~x中任意值，如满足上述公式，n即为x平方根；否则根据（n + x/n）/ 2 得到的值进行递归循环，直至得出结果

实现代码如下：

//牛顿迭代
    public static int newt(int x){
        
        if(x == 0){
        
            return x;
        }
        return (int) ntIteration(x,x);
    }
    
    public static double ntIteration(double n,int x){
        
        double res = (n + (x / n) ) / 2;
        /**
         * 这里面出现了double类型值的比较，
         * 因为double类型值也是有精度的，而这里刚好计算公式耶都一样，
         * 所以如果只要两个值相等，那么这个if语句也是正确的
         */
        if (res == n){
        
            return n;
        }else {
        
            return ntIteration(res,x);
        }
    }

## 总结 ##

二分查找会局限于中间值的乘法而导致数值过大，无法正确计算大于等于100000数值的平方根；  
但是牛顿迭代算法不会出现这种情况。