实现 int sqrt(int x)函数,计算并返回 x 的平方根。
样例 sqrt(3) = 1 sqrt(4) = 2 sqrt(5) = 2 sqrt(10) = 3
这道题是典型的二分法的运用
class Solution {
/**
* @param x: An integer
* @return: The sqrt of x
*/
public int sqrt(int x) {
// write your code here
if (x == 1 || x == 0) {
return x;
}
int left = 1;
int right = x;
while (left < right - 1) {
int mid = left + (right - left) / 2;
int quo = x / mid;
if (quo == mid) {
return quo;
// mid is too big
} else if (quo < mid) {
right = mid;
} else {
left = mid;
}
}
return left;
}
}