题目描述
在一个非降序列中，查找与给定值最接近的元素
输入格式
第一行一个整数
𝑛
n，第二行
𝑛
n 个整数
𝑎
𝑖
a
i
表示要查找的有序数列，第三行若干个整数
𝑚
𝑖
m
i
表示要询问最接近元素的给定值（最多有
𝑆
S 个）。
输出格式
对于每一个
𝑚
𝑖
m
i
，输出其最接近相应给定值的元素值，若有多个值满足条件，输出最小的一个，用空格间隔。
样例
Input 1
4
2 5 9 10
1 2 3 7
Output 1
2 2 2 5
样例解释
给定的序列为[2, 5, 9, 10]，要找到与给定值7最接近的元素。在该序列中，与给定值最接近的元素是5，因此输出为5。
数据范围
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[1000005],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=0x7f7f7f7f;
while(l<=r){
int mid=(l+r)/2;
if(abs(a[mid]-s)<y){
x=a[mid];
y=abs(a[mid]-s);
r=mid-1;
}else if(a[mid]>s){
r=mid-1;
}else{
l=mid+1;
}
}
cout<<x<<" ";
}
return 0;
}