```
int mySqrt(int x) {
if (x <= 1) return x;
int left = 1;
int right = x;
while (left < right) {
int mid = (left + right) / 2;
if (x / mid == mid) return mid;
else if (x / mid > mid)
if (x / (mid + 1) < mid + 1) return mid;
else left = mid + 1;
else right = mid - 1;
}
return left;
}
```