220419 x的平方根的整数

方法一：二分法

public class SqrtX {
    public static void main(String[] args) {
        System.out.println(binarySearch(25));
    }
    /**
     * 二分法
     * @param x
     * @return
     */
    private static int binarySearch(int x) {
        int index = -1, l = 0, r = x;
        while (l <= r) {
            int middle = l + (r - l )/2;
            if (middle * middle <= x) {
                index = middle;
                l = middle + 1;
            } else {
                r = middle - 1;
            }
        }
        return index;
    }
   }

方法二：牛顿迭代

public class SqrtX {

    public static void main(String[] args) {
        System.out.println(newton(24));
    }

    /**
     * 牛顿迭代
     * @param i
     * @return
     */
    private static int newton(int i) {
        if (i == 0) {
            return 0;
        }
        return (int)sqrt(i,i);
    }

    /**
     * 牛顿迭代的思路就是：根号i 一定在 i/n 和 n 之间，然后 (i/n+n)/2 在无限接近于 根号i，所以递归找到 根号i
     *  当 根号i = n时，i/n = n --> (i/n+n)/2 = n;
     * @param n
     * @param i
     * @return
     */
    public static double sqrt(double n, int i) {
        double res = (i/n + n)/2;
        if (res == n) {
            return n;
        } else {
            return sqrt(res,i);
        }
    }

}