[LeetCode] Sqrt(x)
1564 ワード
Implement
Compute and return the square root of x.
@2013-10-07
ちょっと余計なことをしたような気がします.
int sqrt(int x)
. Compute and return the square root of x.
class Solution {
public:
int sqrt(int x) {
int l = 0, r = 46340;
if (r*r <= x) return r;
while (l < r) {
if (r - l < 2) {
if (r*r == x) return r;
return l;
}
int m = (r+l) / 2;
int t= m*m;
if (t == x) return m;
else if (t > x) r = m;
else l = m;
}
}
};
@2013-10-07
ちょっと余計なことをしたような気がします.
class Solution {
public:
int sqrt(int x) {
int left = 0, right = 1;
while (right * right < x) {
if (right * right > INT_MAX / 4) {
left = right;
// sqrt(INT_MAX) = 46340.9
right = 46340;
break;
}
left = right;
right *= 2;
}
int mid, t;
while (right - left > 1) {
mid = (right + left) / 2;
t = mid * mid;
if (t == x) return mid;
else if (t < x) left = mid;
else right = mid;
}
if (right * right > x) return left;
else return right;
}
};