Implement int sqrt(int x).
Compute and return the square root of x.
求一个整数x的平方根,返回int类型。
首先过滤x为负数的错误输入;
其次x是0或者1的情况可以直接返回;
其余情况用二分法,左边界初始为1,右边界初始为x,最需要注意的地方是防止越界错误。为防止middle越界,middle求值表达式应写为middle = left + (right - left) / 2,判断middle和x的关系时,如果写成middle * middle == x会有越界bug。
public int mySqrt(int x) {
if (x < 0) {
return 0;
}
if (x == 0 || x == 1) {
return x;
}
int left = 1, right = x;
while (left + 1 < right) {
int middle = left + (right - left) / 2;
if (middle == x / middle) {
return middle;
} else if (middle > x / middle) {
right = middle;
} else {
left = middle;
}
}
if (right <= x / right) {
return right;
}
return left;
}