QUESTION:

Implement int sqrt(int x).

Compute and return the square root of x.

EXPLANATION:

最好的方法应该是牛顿迭代法吧？反正我这边是用的二分法进行的。

我也把牛顿迭代写在下面吧。

SOLUTION:

public class Solution {
    public int mySqrt(int x) {
        if(x==0) return x;
        int left = 1,right = x;
        while (true){
            int middle = left+((right - left)>>1);

            if(middle>x/middle){
                right = middle-1;
            }else{
                if(middle+1>x/(middle+1)) return middle;
                left = middle+1;
            }
        }
    }
}

public class Solution {
    public int mySqrt(int x) {
        long r = x;
        while (r*r > x)
            r = (r + x/r) / 2;
        return (int) r;
    }
}