查找

绝区零YYDS

2023-08-14 15:31:05

发布于：广东

17阅读

0回复

0点赞

#include<bits/stdc++.h>
using namespace std;
int a[100019],n;
int find1(int k){
	int l=0,r=n-1;
	while(l<r){
		int m=l+r>>1;  //m = (l+r)/2;
		if(k<=a[m])r = m;
		else l = m + 1;
	}
	if(a[l]==k) return l;
	return -1;
}
//5.二分查找模版2  找第一个小于等于k的数
int find2(int k){
	int l=0,r=n-1;
	while(l<r){
		int m=l+r+1>>1;  //m = (l+r)/2;
		if(k>=a[m])l = m;
		else r = m - 1;
	}
	if(a[l]==k) return l;
	return -1;
} 
int main(){
    int t,k;
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    sort(a,a+n);
    cin>>t;
    while(t--){
        cin>>k;
        int fl=find1(k);
        if(fl==-1)cout<<0<<endl;
        else cout<<find2(k)-fl+1<<endl;
    }
    return 0;
}