image.png

注意min的类型 long long

class Solution {
public:
    int mySqrt(int x) {
        if(x == 0) return 0;
        if(x == 1) return 1;
        int lb = 1;
        int ub = x;
        long long mid = 0;
        while(lb + 1 < ub){
            mid = lb + (ub - lb) / 2;
            if(mid * mid == x) return mid;
            if(mid * mid < x) lb = mid;
            else ub = mid;
        }
        return lb;
    }
};