题目
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1:
输入: 4
输出: 2
示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,
由于返回类型是整数，小数部分将被舍去。
思路
使用二分法上界是 x/2+1
代码
class Solution {
public int mySqrt(int x
) {
int low
= 1, high
= x
/2+1, mid
=0;
long s
;
while(low
<=high
){
mid
= (high
-low
)/2+low
;
s
= (long)mid
*mid
;
if(s
< x
) low
= mid
+1;
else if(s
> x
) high
= mid
-1;
else return mid
;
}
return high
;
}
}
