【算法】求平方根 - 二分法/牛顿迭代

题目

求一个数的平方根，要求返回小于等于平方根的正整数。

原理

二分法

遍历每次取中间数，大了就往小取，小了就往大取，直到取到正确的值。

牛顿迭代

求num的平方根，则是求 num / x 和 x 的均值，这个值会越来越趋近于真正的平方根。
比如求12的平方根，2 * 6 = 12，那么 (2 + 6) / 2的值就会更趋近于平方根。

代码

二分法

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

    private static int sqrtByBinary(int num) {
        int index = -1, l = 0, r = num;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (mid * mid <= num) {
                index = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return index;
    }

牛顿迭代

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

    public static int newtonSqrt(double i, int num) {
        double res = (i + num/i) / 2;
        if (res == i) {
            return (int) res;
        }
        return newtonSqrt(res, num);
    }