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;
}
};
