class Solution {public:    int _sqrt(long long tgt, long long i0, long long i1)    {        long long cand = (i0 + i1) / 2;        if (cand * cand == tgt) return cand;        if (cand * cand > tgt)     return _sqrt(tgt, i0, cand);        else if(cand * cand < tgt)        {            if((cand + 1)*(cand + 1) > tgt) return cand;            if((cand + 1)*(cand + 1) == tgt) return cand + 1;            return _sqrt(tgt, cand + 1, i1);        }    }    int sqrt(int x) {        if (x == 1) return 1;        return _sqrt(x, 1, x/2);    }};