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