*Sqrt(x)

 

 

 

 

 

 

 

Q: 

Implement int sqrt(int x).

Compute and return the square root of x.

A:

这里给出两种实现方法：一是二分搜索，二是牛顿迭代法。

1. 二分搜索

对于一个非负数n，它的平方根不会大于（n/2+1）。在[0, n/2+1]这个范围内可以进行二分搜索，求出n的平方根。

1 public class Solution { 2 public int mySqrt(int x) 3 { 4 5 long i = 0; 6 long j = x / 2 + 1; 7 while (i <= j) 8 { 9 long mid = (i + j) / 2; 10 long sq = mid * mid; 11 if (sq == x) return (int) mid; 12 else if (sq < x) i = mid + 1; 13 else j = mid - 1; 14 } 15 return (int) j; 16 17 } 18 }

reference: 

http://www.cnblogs.com/AnnieKim/archive/2013/04/18/3028607.html

转载于:https://www.cnblogs.com/hygeia/p/4812035.html

相关资源：JAVA上百实例源码以及开源项目