【题目描述】

小A所在的学校又迎来了一年一度的开花活动，有 n 名学生被评为文学优秀奖，m 名学生被评为体育优秀奖。现已知两个奖项获奖同学的编号，每个同学都有唯一的编号。只有同时被评为文学优秀奖和体育优秀奖的学生才能开花，小A想知道开花的名单，请你帮他统计一下。

【输入描述】

第一行两个整数  ，分别表示文学优秀奖和体育优秀奖的获奖人数。

第二行 n 个不同的整数，表示获得文学优秀奖的同学编号。

第二行 m 个不同的整数，表示获得体育优秀奖的同学编号。

所有编号为正整数且不超过  。

【输出描述】

一行若干个空格分隔的整数，表示开花的同学编号，按文学优秀奖的先后次序输出。

【样例输入】

4 4
5 1 7 3
2 3 4 1

【样例输出】

 1 3

【题目分析】

根据样例，我们知道获得文学优秀奖的同学有 5 1 7 3，获得体育优秀奖的同学有 2 3 4 1。那么同时获得文学优秀奖和体育优秀奖的同学是 1 和 3，题目要求按照文学优秀奖获奖顺序输出。故而输出的结果是 3 1。

由于数据最大可能是 10^5，故算法必须优于 O(nlogn)。同时我们需要在体育优秀奖里搜索获得文学优秀奖名单。所以可以考虑用二分查找，这样算法的复杂度为 O(logn)。

1、读入文学优秀奖同学，存入数组 a。

2、读入体育优秀奖同学，存入数组 b。

3、排序数组 b，因为要在体育优秀奖里搜索文学优秀奖名单。

4、遍历数组 a，查看 a[i] 是否在数组 b 中。

【参考代码1】

#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 1e5+6;
const int MAXM = 1e5+6;
int a[MAXN];//文学优秀奖
int b[MAXM];//体育优秀奖
 
int main() {
    //读入数据
    int n,m,i;
 	cin>>n>>m; 
    //读入文学优秀奖
    for (i=0; i<n; i++) {
        cin>>a[i];
    }
    //读入体育优秀奖
    for (i=0; i<m; i++) {
          cin>>b[i];
    }
    //排序
    sort(b, b+m);
    for (i=0; i<n; i++) {
        if (binary_search(b, b+m, a[i])) {
            cout<<a[i]<<" ";
        }
    }
    printf("\n");
 
    return 0;
}

【参考代码2】

#include<bits/stdc++.h>
using namespace std;
int t[100005];
int w[100005];
int binary_search(int x, int l, int r){
    while(l <= r){
        int mid = (l + r) >> 1;
        if(t[mid] == x){
            return mid;
        }
        if(t[mid] < x){
            l = mid + 1;
        }else{
            r = mid - 1;
        }
    }
    return -1;
}
int main(){
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < n; ++i){
        cin >> w[i];
    }
    for(int i = 0; i < m; ++i){
        cin >> t[i];
    }
    sort(t, t + m);
    int t = 0;
    for(int i = 0; i < n; ++i){
        if(binary_search(w[i], 0, m - 1) != -1){
            t++;
            if(t == 1) cout << w[i];
            else{
                cout << " " << w[i];
            }
            
        }
    }
    return 0;
}