整数二分与浮点数二分
- 二分的数学思想:
- 一、整数二分
-
- 1、思路
- 2、模板
-
- C++版
- 二、浮点数二分
-
- 1、思路:
- 2、代码:
-
- C++版
- C
二分的数学思想:
二分的数学思想其实就是极限,我们通过取中点的方式,不断地缩小答案所在的区间,让这个区间不断地逼近答案,类似于我们在高数中所学的极限:
一、整数二分
1、思路
我们假设想要寻找上述数轴中的左右边界。
我们先看左边界中的A点,不看B点。我们仔细观察一下A点处符合的性质。
根据上图中的性质,我们就可以开始写二分了。
根据刚刚的描述二分是一个不断逼近地过程,可以理解为两侧端点不断靠近的过程。
将左端点的下标设为
令
如果
那么知道这个有什么用呢?
这就说明
如果
而
如果
如果
通过上面对
通过一轮的比较,我们发现两端的端点再向中间靠拢。
因此我们只需要重复上面的比较,当左端点和右端点合并到一起的时候,那个点就是区间的左端点
接着我们考虑区间的右端点。
右端点就是
我们求出一个中点
如果
那么
接着如果
那么
如果
因此如果
但是我们找左端点的时候,
为什么呢?
我们看下面这个极端的例子:
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位小数,那么必定存在一个范围都是满足这个答案的,因为通过四舍五入后,这个范围的答案都是正确的。此时我们就可以利用浮点数二分。
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;
}
版权声明:本文为博主作者:Turing_Sheep原创文章,版权归属原作者,如果侵权,请联系我们删除!
原文链接:https://blog.csdn.net/weixin_72060925/article/details/127835264