题目描述
实现 int sqrt(int x) 函数。 计算并返回 x 的平方根，其中 x 是非负整数。 由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
Example1:
输入: 4 输出: 2
Example2:
输入: 8 输出: 2 说明: 8 的平方根是 2.82842…, 由于返回类型是整数，小数部分将被舍去。
递归版本
C++代码
class Solution {
public:
int mySqrt(int x) {
// long long res = 1;
// while(res * res <= (long long)x){
// res ++;
// }
// return res - 1;
if(x == 1){
return 1;
}
int left = 1;
int right = x / 2;
while(left < right){
int mid = (left + right) / 2;
if(mid == x / mid){
return mid;
}
else if(mid > x / mid){
right = mid - 1;
}else{
left = mid + 1;
}
}
if(left > x / left){ // 判断求出的left平方是否大于x
return left - 1;
}
return left;
}
};
