01：查最接近的元素
01：查最接近的元素
总时间限制: 1000ms 内存限制: 65536kB
描述
在⼀个⾮降序列中，查与给定值最接近的元素。
输⼊
第⼀⾏包含⼀个整数n，为⾮降序列长度。1 <= n <= 100000。
第⼆⾏包含n个整数，为⾮降序列各元素。所有元素的⼤⼩均在0-1,000,000,000之间。
第三⾏包含⼀个整数m，为要询问的给定值个数。1 <= m <= 10000。
接下来m⾏，每⾏⼀个整数，为要询问最接近元素的给定值。所有给定值的⼤⼩均在0-1,000,000,000之间。
输出
m⾏，每⾏⼀个整数，为最接近相应给定值的元素值，保持输⼊顺序。若有多个值满⾜条件，输出最⼩的⼀个。样例输⼊
3
2 5 8
2
10
5
样例输出
8
5
经典的⼆分查问题。这⾥新添加两段⽐较好的代码：
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<math.h>
4int fun(int a[],int n,int t)
5 {
6int L,R,mid;
7int x,y;
8 L=0;R=n-1;
9while(L<=R)
10 {
11 mid=L+(R-L)/2;
12if(a[mid]==t) return a[mid];
13else if(a[mid]<t) L=mid+1;
14else R=mid-1;
15 }
16 x=abs(a[L]-t);
17 y=abs(a[R]-t);
18if(x<y) return a[L];
19else if(x>y) return a[R];
20else return (a[L]<a[R]?a[L]:a[R]);
21 }
22int main(int argc, char *argv[])
23 {
24int n,a[100003],m,t,i,res;
25 scanf("%d",&n);
26for(i=0;i<n;i++) scanf("%d",&a[i]);
27 scanf("%d",&m);
28for(i=0;i<m;i++)
29 {
30 scanf("%d",&t);
31
32if(t<a[0]) res=a[0];
33else if(t>a[n-1]) res=a[n-1];
34else res=fun(a,n,t);
35
36 printf("%d\n",res);
37 }
38return0;
39 }
View Code
这⾥对上述代码做⼀个样例跟踪演⽰：
假设⽬标t=10048.序列如下：
上图描述的是⽬标t=10048时，上述程序执⾏过程中⼆分查函数⾥⾯L与R的变化过程。下⾯是另⼀个
代码，跟上述的思路基本⼀致。
1//来⾃ttps://blog.csdn/qq_33837704/article/details/80314377
2 #include<iostream>
3 #include<string.h>
4using namespace std;
5int n,m,target;
6int base,top,mid=0;
7long long nums[100010];
8int main(){
9 memset(nums,-1,sizeof(nums));
10 cin>>n;
11for(int i=0;i<n;i++){
12 cin>>nums[i];
13 }
14 cin>>m;
15while(m--){
16 cin>>target;
17base=0;
18 top=n-1;
19while(base<=top){
20 mid=(base+top)/2;
21if(nums[mid]==target){
22break;;
23 }else if(nums[mid]<target){
24base=mid+1;
25 }else {
26 top=mid-1;
27 }
28 }
29if(nums[mid]==target){
30 cout<<target<<endl;
31 }else{
32if(base>=n||base<0){
33 cout<<nums[top]<<endl;
34 }else if(top>=n||top<0){
35 cout<<nums[base]<<endl;
36 }else{
37if(abs(nums[base]-target)>abs(nums[top]-target)){
38 cout<<nums[top]<<endl;
39 }else{
40if(abs(nums[base]-target)<abs(nums[top]-target)){
41 cout<<nums[base]<<endl;
42 }else{
43if(base<top){
44 cout<<nums[base]<<endl;
45 }else{
46 cout<<nums[top]<<endl;
47 }
48 }
49 }
50 }
51 }
52 }
53 }
View Code
假设⽬标t=10092，那么⼆分过程如下：
假设⽬标t=10006，那么⼆分查过程如下：
1 #include<stdio.h>
2 #include<stdlib.h>
3int main(int argc, char *argv[])
4 {
5int n,i,*a,m,t;
6int begin,end,mid;
7int x,y;
8
9 scanf("%d",&n);
10 a=(int *)malloc(n*sizeof(int));
11for(i=0;i<n;i++) scanf("%d",&a[i]);
12
13 scanf("%d",&m);
14for(i=0;i<m;i++)
15 {
16 scanf("%d",&t);
17if(a[0]>t) { printf("%d\n",a[0]); continue;}
18else if(a[n-1]<t) { printf("%d\n",a[n-1]); continue;}
19
20 begin=0;
21 end=n-1;
22 mid=(begin+end)/2;
23while(begin<=end) //while(end-begin>1)
24 {
25if(a[mid]==t) { printf("%d\n",a[mid]);break;}printf怎么读的
26else
27 {
28if(a[mid]>t)
29 {
30 end=mid-1;
31 }
32else
33 {
34 begin=mid+1;
35 }
36 }
37 mid=(begin+end)/2;
38 }
39if(a[mid]!=t)
40 {
41 x=abs(a[begin]-t);
42 y=abs(a[end]-t);
43if(x<y) printf("%d\n",a[begin]);
44else if(x>y) printf("%d\n",a[end]);
45else printf("%d\n",(a[begin]<a[end]?a[begin]:a[end]));
46 }
47 }
48free(a);
49return0;
50 }
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<math.h>
4int fun(int a[],int n,int t)
5 {
6int L,R,mid;
7int x,y;
8 L=0;R=n-1;
9while(L<=R)
10 {
11 mid=L+(R-L)/2;
12if(a[mid]==t) return a[mid];
13else if(a[mid]<t) L=mid+1;
14else R=mid-1;
15 }
16 x=abs(a[L]-t);
17 y=abs(a[R]-t);
18if(x<y) return a[L];
19else if(x>y) return a[R];
20else return (a[L]<a[R]?a[L]:a[R]);
21 }
22int main(int argc, char *argv[])
23 {
24int n,a[100003],m,t,i,res;
25 scanf("%d",&n);
26for(i=0;i<n;i++) scanf("%d",&a[i]);
27 scanf("%d",&m);
28for(i=0;i<m;i++)
29 {
30 scanf("%d",&t);
31if(n==1) res=a[0]; //这个重要
32else if(t<a[0]) res=a[0];//这个重要
33else if(t>a[n-1]) res=a[n-1];//这个重要34else res=fun(a,n,t);
35
36 printf("%d\n",res);
37 }
38return0;
39 }
View Code
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论