Sqrt(x)(Medium)

Implement int sqrt(int x).

Compute and return the square root of x.

对于一个非负数n，它的平方根不会大于（n/2+1）

在中间过程计算平方的时候可能出现溢出，所以用long。

 public int sqrt(int x) {
    long i = 0;
    long j = x / 2 + 1;

    while (i <= j) {
        long mid = (i + j) / 2;
        if (mid * mid == x)
            return (int)mid;
        if (mid * mid < x)
            i = mid + 1;
        else
            j = mid - 1;
    }
    return (int)j;
}

My idea is, for any non-negative number N, sqrt(N) = 2/2sqrt(N) =2sqrt(1/4)sqrt(N) = 2sqrt(N/4). And for the Ns that are not multiple of 4, for example, 9, 25 or 49, the actual result should be 1+2*sqrt(N/4), because we need to take remainders into account.

public int mySqrt(int x) {
    if(x < 4) return x == 0 ? 0 : 1;
    int res = 2 * mySqrt(x/4);
    if((res+1) * (res+1) <= x && (res+1) * (res+1) >= 0) return res+1;
    return res;
}