1.描述
Implement int sqrt(int x).
Compute and return the square root of x.
2.分析
二分法简单题
3.代码
int mySqrt(int x) {
if (x <= 0) return 0;
if (x <= 3) return 1;
int low = 2;
int high = x / 2;
long long mid = (low + high) / 2;
for (;;) {
if (mid * mid == x) return mid;
if (mid * mid > x) high = mid -1;
else if ((mid + 1) * (mid + 1) > x) return mid;
else low = mid + 1;
mid = (low + high) / 2;
}
}
