第二章：整数二分与浮点数二分（极限思想）

阅读本书更多章节>>>>

整数二分与浮点数二分

二分的数学思想：一、整数二分1、思路2、模板C++版 二、浮点数二分1、思路：2、代码：C++版C

二分的数学思想：

二分的数学思想其实就是极限，我们通过取中点的方式，不断地缩小答案所在的区间，让这个区间不断地逼近答案，类似于我们在高数中所学的极限：

一、整数二分

1、思路

我们假设想要寻找上述数轴中的左右边界。

我们先看左边界中的A点，不看B点。我们仔细观察一下A点处符合的性质。

根据上图中的性质，我们就可以开始写二分了。

根据刚刚的描述二分是一个不断逼近地过程，可以理解为两侧端点不断靠近的过程。

将左端点的下标设为 l l l，右端点下标设为 r r r，中间点的下标设为 m i d mid mid， m i d = ( l + r ) / 2 mid = (l+r)/2 mid=(l+r)/2

令 l = 0 l=0 l=0, r = n − 1 r=n-1 r=n−1

如果 m i d mid mid处所对的元素值小于 4 4 4，说明我们的端点 A A A一定不在 m i d mid mid点处，又因为这个序列是单调递增的，所以 m i d mid mid左侧的数字都是小于 m i d mid mid所对的值的。也就是说 m i d mid mid左侧的数字都是小于 4 4 4的，而我们的 A A A处是等于 4 4 4的。

那么知道这个有什么用呢？

这就说明 m i d mid mid的左侧包括 m i d mid mid都不可能是 A A A点，所以我们可以让 l = m i d + 1 l = mid + 1 l=mid+1。

如果 m i d mid mid处所对的值是大于等于 4 4 4的，说明 m i d mid mid右侧的值也一定是大于等于 4 4 4的。

而 m i d mid mid处的值也是等于 4 4 4的，也就是说 m i d mid mid处可能是答案，此时我们考虑一下 m i d mid mid右侧的情况。

如果 m i d mid mid右侧的值都比 m i d mid mid大，那么 m i d mid mid右侧的树也不可能是答案，因为他们都大于 4 4 4。

如果 m i d mid mid右侧还有等于 4 4 4的值，但这些不可能是答案，因为我们找的是区间的左端点，如果 m i d mid mid处是 4 4 4，那么 m i d mid mid右侧的 4 4 4肯定不是左端点。

通过上面对 m i d mid mid右侧的讨论，我们发现 m i d mid mid右侧都不可能是答案，但是 m i d mid mid处有可能是答案。所以我们可以扔掉 m i d mid mid右侧的数，即直接让 r = m i d r = mid r=mid。

通过一轮的比较，我们发现两端的端点再向中间靠拢。

因此我们只需要重复上面的比较，当左端点和右端点合并到一起的时候，那个点就是区间的左端点 A A A。

接着我们考虑区间的右端点。

右端点就是 B B B点，还是和刚才的思路一样，B点一定在这个数轴上，所以我们让左端点 l l l指向起点 0 0 0，右端点 r r r指向最后一个元素下标的 n − 1 n-1 n−1。

我们求出一个中点 m i d mid mid，

如果 m i d mid mid处所对的值是大于4的。

那么 m i d mid mid处肯定不符合条件，由于这个序列是单调递增的，所以 m i d mid mid右侧的数字也一定是大于4的，即不符合条件的。因此，我们可以直接扔掉 m i d mid mid所对的点和它右面的点。即 r = m i d − 1 r = mid - 1 r=mid−1

接着如果 m i d mid mid处所对的值是小于等于4的。

那么 m i d mid mid处有可能是答案，然后我们考虑 m i d mid mid左侧的值。

如果 m i d mid mid左侧的值都是小于4的，那么 m i d mid mid左侧的数字肯定不是答案，可以直接扔掉，如果 m i d mid mid左侧存在等于4的数，这些4也不可能是答案，因为我们找的是右端点，mid在这些4的右面。所以也可以扔掉。

因此如果 m i d mid mid处所对的值，我们可以直接扔掉 m i d mid mid左侧的数，但是需要保留 m i d mid mid，即 l = m i d l=mid l=mid

但是我们找左端点的时候， m i d = ( l + r ) / 2 mid=(l+r)/2 mid=(l+r)/2，而现在由于除法是下取整，所以mid的算法是 ( l + r + 1 ) / 2 (l+r+1)/2 (l+r+1)/2。

为什么呢？

我们看下面这个极端的例子：

2、模板

我们以下面的题目为例：

上述题目来自acwing网站

C++版

#include<iostream>using namespace std;const int N=1e6+10;int arr[N];int main(){    int n,m;    scanf("%d %d",&n,&m);    for(int i=0;i<n;i++)scanf("%d",&arr[i]);    while(m--)    {        //输入要查找的数字        int f=0;        cin>>f;        //开始二分：        //寻找左边界        int l=0,r=n-1;        int mid;        while(l<r)        {            mid=(l+r)>>1;            if(arr[mid]>=f)r=mid;            else l=mid+1;                    }        if(arr[l]!=f)cout<<"-1 -1"<<endl;        else        {            cout<<l<<" ";            //寻找右边界            l=0,r=n-1;                       while(l<r)            {                mid=(l+r+1)>>1;                if(arr[mid]<=f)l=mid;                else r=mid-1;            }            cout<<r<<endl;        }    }        return 0;}

二、浮点数二分

1、思路：

假设我们想求一个数字的立方根，并且要保留6位小数，那么必定存在一个范围都是满足这个答案的，因为通过四舍五入后，这个范围的答案都是正确的。此时我们就可以利用浮点数二分。

所以浮点数二分的思想就是，我们让l到r所组成的区间全部落在答案所在的范围内。此时我们在输出答案即可。

来自acwing。

2、代码：

C++版

#include<iostream>using namespace std;double x;double l=-10000.00;double r=10000.00;int main(){    cin>>x;    while(r-l>1e-10)    {        double mid=(r+l)/2;        if(mid*mid*mid>=x)r=mid;        else l=mid;    }    printf("%.6lf",l);;    return 0;}

C

#include<stdio.h>double x;double l=-10000.00;double r=10000.00;int main(){    scanf("%lf",&x);    while(r-l>1e-10)    {        double mid=(r+l)/2;        if(mid*mid*mid>=x)r=mid;        else l=mid;    }    printf("%.6lf",l);;    return 0;}

阅读本书更多章节>>>>

本文链接：https://www.kjpai.cn/gushi/2024-03-25/148616.html，文章来源：网络cs，作者：胡椒，版权归作者所有，如需转载请注明来源和作者，否则将追究法律责任！