这里只是写了一个简单的二分代码,和雨巨的说法一样,但是只是写法不一样,其他的都是一样的
其中,第一个算法,使用的是二分查找第一个>=x的值,这里需要注意一下:
1:>=x,判断条件那里是>=x;
2:是第一个,所以l,r的赋值,变化要搞清楚;
3:最后返回的值,应该是l+1;因为是找第一个>=x的值,所以,返回l+1;我们不能保证r在过程重会不会越界
另外,找到最后一个<=y的值的分析结果与此类似,相反讨论就好
代码如下:
#include<bits/stdc++.h>//二分法找出大于等于x小于等于y的数有几个 using namespace std; const int N=10010; int a[N]; int binary1(int l,int r,int x){//找出第一个>=x的值; int mid; while(l<r){ mid=(l+r)/2; if(a[mid]>=x) r=mid-1; else l=mid+1; } return l+1; } int binary2(int l,int r,int y){//找出最后一个<=y的值 int mid; while(l<r){ mid=(l+r)/2; if(a[mid]<=y) l=mid+1; else r=mid-1; } return r+1; } int main() { int n; cin>>n; int x,y; cin>>x>>y; for(int i=0;i<n;i++) cin>>a[i]; int l=binary1(0,n-1,x); int r=binary2(0,n-1,y); cout<<"第一个>=x的序号为:"<<l<<" 最后一个<=y的序号为"<<r<<endl; cout<<"区间个数为:"<<r-l+1<<endl; return 0; }这里是二分法的基本应用,后面用二分法中函数就可以解决,但是在正式解决问题时,会用到二分法的思想,例如:归并排序,快速排序,都会用到,所以,这里还是将二分法最基础的写法写了一遍~