```
class Solution {
int mySqrt(int x, int begin, int end) {
if (begin + 1 >= end) return begin;
int mid = begin + (end - begin) / 2;
if (x / mid < mid) return mySqrt(x, begin, mid);
return mySqrt(x, mid, end);
}
public:
int mySqrt(int x) {
if (x == 0) return 0;
return mySqrt(x, 1, x);
}
};
```