题目描述
输入
𝑁
(
𝑁
<
1
0
6
)
N(N<=10
6
) 个从小到大的有序数，用二分查找给定数
𝑀
M 的个数，输出对应的个数，若无此数输出
0
0;
输入格式
第一行一个整数
𝑛
n，第二行
𝑛
n 个整数
𝑎
𝑖
a
i
表示要查找的有序数列，第三行若干个整数
𝑚
𝑖
m
i
表示要查找的数字（最多有
𝑆
S 个）。
输出格式
对于每一个
𝑚
𝑖
m
i
，输出其个数，若无此数输出 0;，用空格间隔，如果不存在，则输出 0。
样例
Input 1
5
1 2 2 2 5
2
Output 1
3
数据范围
0
<
𝑛
≤
1
0
6
0<n≤10
6
，
0
≤
𝑎
𝑖
≤
1
0
9
0≤a
i
≤10
9
，
0
≤
𝑚
𝑖
≤
1
0
9
0≤m
i
≤10
9
，
0
<
𝑆
≤
10000
0<S≤10000。
#include<bits/stdc++.h>
using namespace std;
int n,a[100005],s;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
while(cin>>s){
int l=1,r=n,x=0,y=0;
while(l<=r){
int mid=(l+r)/2;
if(a[mid]==s){
x=mid;
r=mid-1;
}else if(a[mid]>s){
r=mid-1;
}else{
l=mid+1;
}
}
l=1,r=n;
while(l<=r){
int mid=(l+r)/2;
if(a[mid]==s){
y=mid;
l=mid+1;
}else if(a[mid]>s){
r=mid-1;
}else{
l=mid+1;
}
}
if(!x&&!y){
cout<<0<<" “;
continue;
}
cout<<y-x+1<<” ";
}
return 0;
}