简单算法二分

ygxdsh

~~相信很多友友们对算法很感兴趣，下面就让小编带大家看看简单的二分算法吧~~
营销号时间结束了，我们来玩个小游戏吧！
数字炸弹：答案是1-100中随机的一个数，假设你每次询问1-100中的一个数n，得到的回答只“猜对了！”，“比n大”或者“比n小”。怎么才能用最小的询问次数得到答案呢？
聪明的你一定能想到“我第一次直接询问50，范围不就缩小一半了吗？”
对，这就是二分。
将一个大范围缩小成两个小范围（并保留符合条件的那一个），即为二分。
让我们看看这个问题的代码实现吧。

#include <stdio.h>

int main()
{
    int m;
    scanf("%d", &m);

    int l = 1, r = 100; // l,r分别表示区间的左右边界
    while (l < r)
    {
        int mid = (l + r) / 2;//mid即l和r的中间值
        if (mid < m)
            l = mid + 1;//中间值mid比答案小，则将左边界l更新为mid+1
        else
            r = mid;//否则将右边界更新为mid
            //（不是mid-1是因为m可能等于mid，后面在详细讨论此问题）
    }

    //退出while循环后l和r相同且都是所需答案，任意输出一个即可
    printf("%d", l);
    return 0;
}

中间while循环的那一部分就是最简单的一个二分代码。
那么现在我们就对于二分有了一个基本的概念。
所以
为什么要学二分呢，又或者说二分有什么用呢？
相信刚接触算法题的大家遇到的最多的报错之一就是运行超时。
算法题，故名思意考的是算法，而算法就是通过一种奇妙的魔法降低代码完成同一任务的复杂度。
复杂度分为时间复杂度和空间复杂度。
而二分就是优化时间复杂度的一种好方法。
回想我们刚才的数字炸弹游戏。
如果不使用二分我们从1-100一个一个问，最不理想的情况是需要问100次。
而因为我们使用了二分每次询问就能缩小一半的范围，所以假设询问次数是o，最差的情况也就是2的o次方等于100，询问次数也就是log以2为底100的对数（算法中讨论复杂度常将log以2为底简写为log）
假如我们把范围设为n，那么二分就将时间复杂度为n代码优化成了时间复杂度为logn的代码，可以简写为将o（n）优化为o（logn）。
用你小学一年级的数学知识不难知道，这里的n越大，优化效果就越好。

竟然知道了二分的强大作用，那接下来我们来系统的学一下二分吧！！！

1.整数二分

这里还是拿一个题目来举例

数的范围

给定一个按照升序排列的长度为 n 的整数数组，以及 q 个查询。

对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 00 开始计数）。

如果数组中不存在该元素，则返回 `-1 -1`。

这个题目和我们上面的游戏最大的不同是什么呢？
数字炸弹可以看作是顺序存了的1-100的长度为100的数组，去找其中一个数。
而这一题最大的问题是数组中可能出现重复的数，
我们要分别找到第一个k的位置和最后一个k的位置。

我们先把上面的二分模板复制过来简单修改一下

int l = 0, r = n - 1;
//n是数组长度,l和r分别表示数组下标的左右边界
while (l < r)
{
    int mid =(l + r) / 2;
    if (q[mid] < k) 
		l = mid + 1;
    else 
	    r = mid;
}

可以发现当满足q[mid]==k时这段代码修改的是右边界r的值
考虑特殊情况当q[l]==q[r]==k时右边界r一直向左边界l靠近
所以最后当l==r时，l和r应该都是第一个等于k的数的下标
数组中不存在等于k的数，则最后的结果会导致l>r

现在我们知道了如何找到第一个k的位置，接下来就只需要找到最后一个k的位置。
根据刚才的找到第一个k的位置的思路，我们可以推断出
当满足q[mid]==k时修改左边界l的值就可以找到最后一个k的位置。
代码如下

int l = 0, r = n - 1;

while (l < r)
{

    int mid =(l + r + 1) / 2;
    if (q[mid] <= k)
        l = mid;
    else
        r = mid - 1;
}

这样就可以找到最后一个k的位置啦！
不过认真看到这里的小朋友肯定会又有一个疑问
”为什么这里求的mid要多加个1呢？“
微博这种问题称为二分边界问题
可以考虑一种特殊情况，当q[l]==q[r]==k且r-l==1时，
计算出来的mid==l,而因为此时的q[l]==k,所以会执行l=mid，最终陷入无限循环。
此处计算mid时+1就是为了解决这个问题。

讲完了较为复杂的整数二分，接下来我们放松一下，来看看简单的浮点数二分。

2.浮点数二分

同样也是拿一个问题举例：
在使用编程计算一个数的平方根的时候，大家都会想到math库里的sqrt（）函数。
但是朋友们，有没有想过自己怎么手搓一个sqrt（）函数呢！！！
浮点数二分刚好能解决这个问题。
按照惯例，展示代码

double sqrt(double k)
{
    double l = 0, r = 1e9;
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (mid * mid < k)
            l = mid;
        else
            r = mid;
    }
    return l;
}

看起来也是似分的简单啊！！！
这里的eps根据题目所要求的精确到第几位小数而定，
比如题目要求精确小数点后两位，那么eps定为0.001肯定够了。
因为退出循环时l，r差值肯定小于eps，
所以当eps为0.001时，l和r的差值小于0.001，前两位小数也就肯定相同。
eps越小得到的值越准，但是也不一定是越小越好。
可以想象要精确越准，循环的次数越多，所以根据题目要求，设一个合适的就好。

可以发现浮点数二分真的比整数简单许多，因为没有边界问题，也就不需要考虑+1，-1什么的！
最喜欢浮点数的一集！
其实聪明的你一定能想到，对以上代码做一点小小的修改就可以得到求立方根，甚至求四次方以及以上的函数。

那么二分到这就差不多讲完了。

不过上面的二分代码还有一点可优化空间。
例如求mid时，上文一直使用的mid=(l+r)/2
可能看上去没什么问题，不过l和r作为同一种类型的数据，相加可能会爆范围。
例如

	int l = 1e9, r = 2e9;
	int mid = (l + r) / 2;

理论上，mid应该为1.5e9，可却得不到这个结果，我是为什么呢？
因为l+r得到的结果3e9已经超出了int的范围，最终就得不到所需要的mid。
为了解决这个问题，可以将计算mid的代码修改为mid=l+(r-l)/2
是不是很巧妙呢

好的，那么我所了解的二分知识就讲完了（欢迎大佬补充）

最后我们来总结一下，二分的作用就是优化代码的时间复杂度。
那我们什么时候可以使用二分呢？
我的理解是，只要题目中出现了一种规律（大多数时间是单调性）是就能使用二分。
数字炸弹能使用二分是因为1-100是严格递增的一百个数；
讲整数二分时，求数的范围也能使用二分是因为数组中的数是不严格递增（可重复）；