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

本文主要是介绍【算法】求平方根 - 二分法/牛顿迭代，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

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

原理

二分法

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

牛顿迭代

求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);}

这篇关于【算法】求平方根 - 二分法/牛顿迭代的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---