我的CSDN博客： 我的博客

题目描述

请实现 int sqrt(int x)。

请计算并返回 $x$ 的正平方根，保证 $x$ 是一个非负整数。
注意返回类型是整数，所以我们只返回正平方根的整数部分。

样例1

输入：4
输出：2

样例2

输入：8

解题思路：

这道题题目说白了就是复现sort()函数。

由于返回值是整数，所以最简单的方法当然是从$0\rightarrow X$依次进行判断得出答案。

但直接循环会浪费很多时间，在我们玩猜数字游戏的时候，我们都知道可以通过不断折半猜数字，很快的得到答案，而这样的思想就是二分。

而本题就是一个很好展现二分思想的一个例题。

在学习二分的时候发现了个很好用的二分查找算法模板

它将其分成了两个情况，接下来一个一个的进行讲解。（以下两个模板均来自 二分查找算法模板 ）

该模板的算法思路：假设目标值在闭区间 $[l, r]$ 中， 假设 $M$ 是我们最后要的答案，那么这个区间就会被 $M$ 分成两个部分。

而在判断的时候我们是将 $M$ 放在左半部分还是右半部分，就会决定着我们的代码会是一个怎么的样子， 而这两个模板就是针对这两种情况而提供的。

版本一：

int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

版本一是当我们将区间 $[l, r]$ 划分成 $[l, mid]$ 和 $[mid + 1, r]$ 时（既 $M$ 属于右半部分的时候），其更新操作是 $r = mid$ 或者 $l = mid + 1;$ ，计算 $mid$ 时不需要加1。

这个模板中为什么 $l = mid + 1$ 呢？

是因为，当给 $l$ 赋值的时候，是 $mid$ 不在区间的右半部分的时候。又因为答案 $M$ 是在右半部分，所以可以知道 $mid$ 一定不是我们要的答案，因此 $l = mid + 1$ 。（这里是满足区间相邻两个数差值为 $1$时的情况下 $+1$）

版本二：

int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

版本二是当我们将区间 $[l, r]$ 划分成 $[l, mid - 1]$ 和 $[mid, r]$ 时（既 $M$ 属于左半部分的时候），其更新操作是 $r = mid - 1$ 或者 $l = mid;$ ，此时为了防止死循环，计算 $mid$ 时需要加 $1$。

对于为什么 $r = mid - 1$ 是因为，当给 $r$ 赋值的时候，是 $mid$ 不在区间的左半部分的时候。又因为答案 $M$ 是在左半部分，所以可以知道 $mid$ 一定不是我们要的答案，因此 $r = mid - 1$ 。（这里是满足区间相邻两个数差值为 $1$时的情况下 $+1$）

那 $mid = l + r + 1 >> 1$ 是怎么回事呢？

我们可以想一下，若 $l + 1 = r$ 时，我们采用 $mid = l + r>> 1$ 会出现一个什么样的情况？

$$ \because mid = l + r = (2 * l + 1) / 2 = l$$$$\therefore l = mid = l$$$$\therefore区间范围依然是[l, r]$$

所以为了出现这种死循环的情况，我们要这样计算 $mid = l + r + 1 >> 1$ 。

接下来返回我们的题目，首先我们要思考采用它是属于哪一种类型的模板。

最初我以为两个模板都可以使用，于是就直接用了第一个模板来写了一个，最后连样例都没有过…

然后思考后发现，这道题只能采用第二个模板，即答案 $M$ 在左边的情况。

因为我们这道题要求的时 “由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。” 因此如果结果时 $2.333, 2.999, 2.123$ 之类的最后输出都只能是 $2$。

在确定了属于哪种类型后就直接套模板写代码即可。

$AC$代码：

int mySqrt(int x){
    int l = 0, r = x;
    while(l < r){
        int mid = l + (long long)r + 1 >> 1;
        if(mid <= x / mid)
            l = mid;
        else
            r = mid -1;
    }
    return r;
}

需要注意的是防止数据过大而导致数据溢出，上面的代码也做了防止溢出的相应处理。