题目描述
给你一个非负整数
x，计算并返回x的 算术平方根 。由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如
pow(x, 0.5)或者x ** 0.5。示例 1：
输入：x = 4 输出：2示例 2：
输入：x = 8 输出：2 解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。提示：
0 <= x <= 231 - 1
分析
由于输出结果的时候需要将小数部分舍去，因此问题的答案平方以后一定不会大于输入的整数。综上，该题可转变为查找整数的问题：
- 如果这个整数的平方 恰好等于 输入整数，那么我们就找到了这个整数；
- 如果这个整数的平方 严格大于 输入整数，那么这个整数肯定不是我们要找的那个数；
- 如果这个整数的平方 严格小于 输入整数，那么这个整数 可能 是我们要找的那个数。
直觉上，一个整数的平方根肯定不会超过它自己的一半，但是 0 和 1 除外，因此我们可以在 1 到输入整数除以 2 这个范围里查找我们要找的平方根整数。
代码实现
class Solution {
public:
int mySqrt(int x) {
// 特殊值判断
if (x == 0){
return 0;
}
if (x == 1){
return 1;
}
int left = 1;
int right = x / 2;
// 在区间 [left, right] 查找目标元素
while (left <= right) {
int middle = left + ((right - left) / 2);
// 注意：这里为了避免乘法溢出(middle*middle)，改用除法
if (middle > x / middle) { // 猜的数平方以后大了就往小了猜
// 下一轮搜索区间是 [left, middle - 1]
right = middle - 1;
} else if (middle < x / middle) { // 猜的数平方以后小了，可能猜的数就是，也可能不是
// 下一轮搜索区间是 [middle + 1, right]
left = middle + 1;
} else {
return middle; // 猜的数平方以后恰恰好等于输入的数
}
}
return left - 1;
}
};
