Implement int sqrt(int x).
Compute and return the square root of x.
Solution：二分查找
思路： 从1 到 x/2中开始二分查找try mid^2 和 x的大小，注意结束条件。
实现Perfer solution2写法
Note: 如果x是小数类型则不能使用x/2，应该用[0, 1]之间，在限制精度内可以用二分查找
Time Complexity: O(logX) Space Complexity: O(1)
Solution Code：
class Solution1 {
public int mySqrt(int x) {
if (x <= 1) return x;
int left = 1, right = x / 2;
int ans = 0;
while (left <= right) {
int mid = (right + left) / 2;
if(mid == x / mid) return mid;
else if(mid < x / mid) {
ans = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return ans;
}
}
class Solution2 {
public int mySqrt(int x) {
if (x <= 1) return x;
int left = 1, right = x / 2;
while (true) {
int mid = (right + left) / 2;
if(mid == x / mid) return mid;
else if(mid < x / mid) {
if (mid + 1 > x/(mid + 1))
return mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
}
}
