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

墨蓝 2023-10-05 13:21 11阅读 0赞

#### 69. x 的平方根 ####

*  题目
 *  解题思路
 *  代码

## 题目 ##

实现`int sqrt(int x)` 函数。

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

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70_pic_center]

## 解题思路 ##

*  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;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/2020110913171390.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5,size_16,color_FFFFFF,t_70#pic_center