二分查找模板
你需要的都在这里!!!还不赶快收藏???
二分查找
手写代码
#include<iostream>
using namespace std;
int a[1000100];
int main()
{
int p=-1,x,n,left,right,mid;
//p:x的位置 left:左边 right:右边 mid:中间
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
cin>>x;
left=0;
right=n-1;
while(left<=right&&x<=a[n-1])
{
mid=(left+right)/2;//求中间数
//分情况判断
//x在中间
if(a[mid]==x)
{
p=mid+1;
break;//停止循环
}
//x在前一半
else if(x<a[mid]) right=mid-1;
else if(x>a[mid]) left=mid+1;
}
cout<<p;
return 0;
}
函数
binary_search(a+begin,a+end,x,cmp)
需要头文件#include<algorithm>
二分查找左边界
手写代码
#include<iostream>
using namespace std;
long long n,a[100100],q,x,l,r,mid;
long long fun(int x1)
{
l=1;
r=n;
while(l<=r)
{
mid=(l+r)/2;
if(x<a[mid]) r=mid-1;
if(x>a[mid]) l=mid+1;
if(x==a[mid]) r=mid-1;
}
if(a[l]!=x) return -1;
return l;
}
int main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
scanf("%lld",&q);
for(int i=1;i<=q;i++)
{
scanf("%lld",&x);
printf("%lld ",fun(x));
}
return 0;
}
函数
lower_bound(a+begin,a+end,x,cmp)
需要头文件#include<algorithm>
二分查找右边界
手写代码
#include<iostream>
using namespace std;
int n,q,a[100100],x,l,r,m;
int fun(int x)
{
l=1;
r=n;
while(l<=r)
{
m=(l+r)>>1;
if(x<a[m]) r=m-1;
if(x>a[m]) l=m+1;
if(x==a[m]) l=m+1;
}
if(a[r]==x) return r;
else return -1;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
cin>>q;
for(int i=1;i<=q;i++)
{
cin>>x;
cout<<fun(x)<<' ';
}
return 0;
}
函数
upper_bound(a+begin,a+end,x,cmp)
需要头文件#include<algorithm>
哪里呢?
???
我估计她是再问你在哪找到的在脑子里找的。