这题用二分法。
如果mid*mid == x，返回mid；
如果mid*mid < x，那么说明mid过小，应让low = mid+1，在右边继续查找
如果mid*mid > x，那么说明mid过大，应让high = mid-1，在左边继续查找
这里用了long，因为m*m可能超过integer最大值。也可以用可以用 mid < x / mid 来避免用long.
另外也可以用数学里的牛顿法。
//二分法
public int mySqrt(int x) {
long low = 0;
long high = x;// or high = x/2 +1 ;这个规律可以减少一些复杂度
while (low <= high) {
long mid = (low + high) / 2;
if (mid * mid <= x && x < (mid + 1) * (mid + 1)) {
return (int) mid;
} else if (mid * mid > x) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return 0;
}
