题目:
Implement int sqrt(int x).
Compute and return the square root of x.
x is guaranteed to be a non-negative integer.
Example:
Input: 4
Output: 2
Example 2:
Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since we want to return an integer, the decimal part will be truncated.
答案:
class Solution {
public int mySqrt(int x) {
long xi = x;
while(xi * xi > x) {
xi = (xi + x/xi)/2;
}
return (int)xi;
}
}
binary search的解法要注意m*m有可能会overflow，所以要用long变量
class Solution {
public int mySqrt(int x) {
long l = 0, r = (int)Math.ceil(x / 2.0);
while(l <= r) {
long m = l + (r - l) / 2;
if(m * m == x || (m*m < x && (m+1) * (m+1) > x)) {
return (int)m;
}
else if(m * m < x) {
l = m + 1;
}
else {
r = m;
}
}
return 0;
}
}
