69. x 的平方根（二分查找）

69. x 的平方根

• 题目
• 解题思路
• 代码

题目

实现int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

解题思路

• X 平方根的整数部分 k 一定满足 k²<=x.
• 所以我们只要用二分法不断缩小范围找到满足该条件的最大值k
• 下界为0，上界最开始设置为x。我们就只需要在每次二分范围内比较mid²与x的关系，如果大了就缩小上界right
• 小了或等于了就增大下界left

代码

class Solution {
    public int mySqrt(int x) {
        int l = 0, r = x, ans = -1;
        while (l <= r) {//之所以要循环到l>r是为了保证找到的是最大值
            int mid = l + (r - l) / 2;//其实mid就等于(l+r)/2，这里这么写是为了防止溢出
            if ((long) mid * mid <= x) {//用long 也是为了防止mid过大而导致溢出。
                ans = mid;//因为k满足k²<=x，所以结果只会出现在mid²<=x的情况下
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return ans;
    }
}