Implement int sqrt(int x).
Compute and return the square root of x.
Solution：二分查找
思路： 從1 到 x/2中開始二分查找try mid^2 和 x的大小涩笤，注意結(jié)束條件跺涤。
實(shí)現(xiàn)Perfer solution2寫法
Note: 如果x是小數(shù)類型則不能使用x/2，應(yīng)該用[0, 1]之間桶蛔，在限制精度內(nèi)可以用二分查找
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;
}
}
}
}
