Implement int sqrt(int x).
Compute and return the square root of x.
对于一个非负数n，它的平方根不会大于（n/2+1）。在[0, n/2+1]这个范围内可以进行二分搜索（binary search），求出n的平方根。
注：在中间过程计算平方的时候可能出现溢出，所以用long.
Java code:
public class Solution { public int mySqrt(int x) { long i = 0; long j = x / 2 + 1; while(j >= i){ long mid = (i + j) / 2; long sqr = mid * mid; if(sqr == x) { return (int)mid; }else if(sqr < x){ i = mid + 1; }else { j = mid - 1; } } return (int)j; } }
Reference:
1. http://www.cnblogs.com/AnnieKim/archive/2013/04/18/3028607.html
原文：http://www.cnblogs.com/anne-vista/p/4899698.html