题目:

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;
}
}