Sqrt(x)
Discussion
二分查找,注意溢出问题。
Solution
int sqrt(int x) {
if (0 == x) return 0;
int left = 1, right = x, ans;
while (left <= right) {
int mid = left + (right - left) / 2;
if (mid <= x / mid) {
left = mid + 1;
ans = mid;
} else {
right = mid - 1;
}
}
return ans;
}
right = x/2 + 1
也可以。不能比较(mid*mid <=x )
因为可能溢出。