class Solution {
public:
    int mySqrt(int x) {
        if(x == 0) return 0;
        if(x == 1) return 1;
        // 左闭右闭区间
        long long left = 0, right = x/2;
        long long cur = 0;
        while(left <= right){
            long long mid = (left + right)/2;
            if(mid * mid < x){
                cur = mid;
            }
            if(mid * mid == x){
                cur=mid;
                break;
            }else if(mid*mid > x){
                right = mid-1;
            }else{
                left = mid+1;
            }
        }

        return cur;
    }
};