数据结构算法之n的平方根保留m位小数

求n的平方根x，x精确到m位小数。例如求n精确到小数点后4位的平方根。

思路：

求n的平方根x，则首先想到的是可不可以从1开始，分别求1、2、3等的平方，看是否等于n。这里就有个问题我为什么首先从1开始，而且为什么各个数的步长为1？也就是说我们应该从哪里开始去试，每次去试时，各个数的步长应该怎么选？

从上面的分析中得出求n的平方根其实就是从小于n的数中找到x，使x*x等于n，这就变成了一个查找的问题，而且是在有序数据集中查找，则最容易想到的就是二分查找，则从哪里开始去试，每次去试时，各个数的步长问题就都解决了。

下面看下二分查找的代码：

public static int binarySearch(int[] arr, int target){
    int low = 0;
    int high = arr.length-1;
    while (low <= high){
        int mid = (low + high) / 2;
        if (target > arr[mid]){
            low = mid + 1;
        }else if (target < arr[mid]){
            high = mid - 1;
        }else {
            return mid;
        }
    }
    return -1;
}

使用二分查找找到平方根的范围然后递增步长

对于一个数的平方根能够找到该跟的范围，即_xx < n < yy_，则n的平方根在x和y之间，且_x+1=y_。
找到平方根所在的区域之后，把所要保留的精度的平方根做为步长对x进行递增，直到_|n-x*x|<0.0001(精度)_为止。

例如求12的平方根，精度为小数点后2位。代码示例如下：

public static double sqrtByInc(int n, double precision){
    int low = 0;
    int high = n;
    int mid = (low + high) / 2;
    // 二分查找找到平方根的区域
    while (low <= high){
        if (mid * mid > n){
            high = mid - 1;
        }else if (mid * mid < n){
            if ((mid+1)*(mid+1) > n){
                break;
            }
            low = mid + 1;
        }else {
            break;
        }
        mid = (low + high) / 2;
    }
    // 按照精度的平方根做为步长
    double r = mid;
    while (Math.abs(n-r*r) > 0.0001){
        if (r * r < n){
            r += 0.01;
            r = BigDecimal.valueOf(r).setScale(2, RoundingMode.HALF_UP).doubleValue();
        }else {
            break;
        }
    }	
    return r;
}

改进

上面的方法只是用二分查找找到平方根的范围，然后递增步长进行尝试，虽然能够快速找到根的范围，但是递增步长将是一个漫长的等待。

由_|n-x*x|<0.0001(精度)_可得n的平方根减去x小于0.01，n的平方根和x都是根的候选者，则只要只要两个候选者的差值小于0.01，则x就是所要求的平方根。这样就可以直接使用二分查找进行查找。代码如下：

public static String sqrt(int n, double precision){
    double start = 0;
    double end = (double) n;
    double last = end;
    double mid = (start + end) / 2.0;
    while (Math.abs(last - mid) > precision){
        if (mid * mid > n){
            end = mid;
        }else {
            start = mid;
        }
        last = mid;
        mid = (start + end) / 2.0;
    }
    DecimalFormat df = new DecimalFormat("0.00");
    return df.format(mid);
}

迭代计算平方根

对于这种数学类型的问题，使用数学公式应该是最快的。求n的平方根有一个公式可以使用，叫牛顿迭代法。
代码如下：

public static double SqrtByNewton(int n, double precision)
{
    double val = n; //最终
    double last; //保存上一个计算的值
    do
    {
        last = val;
        val =(val + n/val) / 2;
    }while(Math.abs(val-last) > precision);
    return val;
}