*Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

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

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