题目内容

实现 int sqrt(int x) 函数。

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

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

示例

示例 1:

输入: 4
输出: 2

示例 2:

输入: 8
输出: 2
说明: 8 的平方根是 2.82842…, 由于返回类型是整数，小数部分将被舍去。

题解

本题考察二分思想，具体来说就是寻找一个最大的y，使得$y^2$≤x即可。具体实现思路如下，

首先，我们需要思考一下二分的范围，当x在(0,1)内时，y也在(0,1)内；当x在(1,正无穷)时，y在[1,x]内。因此，我们取范围的并集，即[0,x]。

然后，因为$y^2$具有单调性，不论y是否在0和1之间还是大于1，$y^2$一定是单调递增的，因此满足二分的条件。

最后，代码实现上，注意数值不要越界即可。

代码

class Solution {
public:
    int mySqrt(int x) {
        //找出一个最大的y，使得y的平方小于等于x
        //又由于y^2具有单调性，因此可以采用二分的方式
        int l = 0, r = x;
        while (l < r) {
            int mid = l + 1ll + r >> 1;//为了防止越界，1ll是1的long long 类型，在计算的时候，最后的值为一个long long类型 就不会越界了。当l = mid时，上面的mid的定义需要+1
            if (mid <= x / mid) l = mid;
            //if判断中这样写是为了防止越界。
            else r = mid - 1;
        }
        return r;
    }
};