面试高频算法题：求平方根，精确到小数点后n位

前几天面美团的时候被问到了这个问题，自己处理的不是很好，在此重新总结一下。

面试题目要求：求某正整数的平方根，要求误差小于0.01

//二分法进行处理，注意变量类型
 public static double sqrt(int target){
        double n=1e-2;            //在这里可根据精度要求进行调整
        double l=0,r=target;      //这里若初始化r=target/2的话，则处理较小正整数会出错，如1,2
        while(l<=r){              //二分查找
            double mid=(l+r)/2;
            //这里用除法，而不用mid*mid与target比较，是防止mid过大时，mid*mid产生溢出问题
            if(target/mid<mid){   
                r=mid-n;
            }else{
                l=mid+n;
            }
        }
        return r;
    }

验证代码是否正确运行

public class Main {
    public static void main(String[] args) {
       //定义一个8个整数的数组来验证，数组有包括小正整数和较大的正整数
       int[] arr={1,2,6,9,18,65,102,266665898};   
        for(int i=0;i<arr.length;i++) {
            boolean res = Math.abs(sqrt(arr[i])-Math.sqrt(arr[i]))<0.01;
            System.out.println("差距是否小于0.01：   "+ res);                                           //达到精度要求则输出true
        }
    }
    public static double sqrt(int target){
        double n=1e-2;
        double l=0,r=target/2;
        while(l<=r){
            double mid=(l+r)/2;
            if(target/mid<mid){
                r=mid-n;
            }else{
                l=mid+n;
            }
        }
        return r;
    }
}

运行结果

tips

这题也可以用牛顿迭代法来处理，且代码更加简洁。但一些大厂在面试时会告知面试者不能使用牛顿迭代法。所以还是建议采用二分法。