Description

Submission

2147395600 and 2147395599 are two boundary cases.

class Solution {
public:
    int mySqrt(int x) {
        long res = mySqrtBinary(x, 0, x / 2);
        res -= 1;
        while((res + 1) * (res + 1) <= x) res++;
        return res;
    }
private:
    int mySqrtBinary(int x, int a, int b) {
        if(a >= b) return b;
        long mid = (a + b) / 2;
        if(mid * mid < x) {
            return mySqrtBinary(x, mid + 1, b);
        }
        return mySqrtBinary(x, a, mid - 1);
    }
};