LeetCode二分查找：x 的平方根
LeetCode二分查找：x 的平方根
题目描述
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
**注意：**不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1：
输入：x = 4
输出：2
示例 2：
输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
解题思路
经典写法：
用二分查找的思想，通过不断缩小搜索范围，最终找到平方根的整数部分。
为什么采用
long而不是int？因为再计算r时可能出现溢出
需要注意得一点是：在计算 mid 时使用 left+(right-left) / 2，而不是 (left + right) / 2。这样可以避免溢出。
代码
class Solution {
public int mySqrt(int x) {
long high = x / 2;
long low = 0;
if (x == 1) {
return 1;
}
while (low <= high) {
long mid = low + (high - low) / 2;
long r = mid * mid;
if (r > x) {
high = mid - 1;
} else if (r < x) {
low = mid + 1;
} else {
return (int) mid;
}
}
// 返回 low - 1 而不是 low
return (int) (low - 1);
}
}