二分查找应用-计算开平方根

本文主要是介绍二分查找应用-计算开平方根，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题: 计算开平方根

解题思路

1.二分查找，时间复杂度O(nlog(n))，空间复杂度O(1)

2.牛顿法，时间复杂度O(nlog(n))，空间复杂度O(1),收敛速度较快.

代码如下

public static void main(String[] args) {int x = 8;int ans = mySqrt2(x);System.out.println(ans);int ans2 = mySqrt2(x);System.out.println(ans2);}//利用二分查找计算均方根值public static int mySqrt(int x) {//定义long类型，防止大数越界long left = 0;long right = x;while (left <= right) {long middle = (right - left) / 2 + left;if (middle * middle == x) {return new Long(middle).intValue();} else if (middle * middle < x) {left = middle + 1;} else {right = middle - 1;}}return new Long(right).intValue();}//利用牛顿法计算函数零点//迭代公式： x[n+1]=0.5*(x[n]+C/x[n])public static int mySqrt2(int x) {double precision =  1e-1;double C = x;double x0 = x;while (true) {double x1 = 0.5* (x0 + C / x0);if (Math.abs(x1 - x0) < precision) {return new Double(x0).intValue();} else {x0 = x1;}}}

这篇关于二分查找应用-计算开平方根的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---