算法基础课复习第二天<二分>
作者:
骏杰
,
2022-04-29 09:19:09
,
所有人可见
,
阅读 148
二分:
数的范围:
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=100010;
int a[N];
int n,q;
int main()
{
cin>>n>>q;
for(int i=0;i<n;i++) cin>>a[i];
while(q--)
{
int x;
cin>>x;
int l=0,r=n-1;
while(l<r)
{
int mid=l+r>>1;
if(a[mid]>=x) r=mid;
else l=mid+1;
}
if(a[l]!=x) cout<<"-1 -1"<<endl;
else
{
cout<<l<<" ";
int l=0,r=n-1;
while(l<r)
{
int mid=l+r+1>>1;
if(a[mid]<=x)
{
l=mid;
}
else r=mid-1;
}
cout<<l<<endl;
}
}
return 0;
}
数的三次方根:
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=10010;
int main()
{
double x;
cin>>x;
double l=-10000,r=10000;//其实开到100就可以了,题中是三次方
while(r-l>1e-8)//浮点二分,保留6位小数,开到8位,然后二分时候边界卡的没有那么死
{
double mid=(l+r)/2;
if(mid*mid*mid>=x)
{
r=mid;
}
else l=mid;
}
printf("%.6lf\n",l);
return 0;
}