P1571 眼红的Medusa

题目描述
虽然 Miss Medusa 到了北京，领了科技创新奖，但是他还是觉得不满意。原因是：他发现很多人都和他一样获了科技创新奖，特别是其中的某些人，还获得了另一个奖项——特殊贡献奖。而越多的人获得了两个奖项，Miss Medusa就会越眼红。于是她决定统计有哪些人获得了两个奖项，来知道自己有多眼红。

输入格式
第一行两个整数 n, mn,m，表示有 nn 个人获得科技创新奖，mm 个人获得特殊贡献奖。

第二行 nn 个正整数，表示获得科技创新奖的人的编号。

第三行 mm 个正整数，表示获得特殊贡献奖的人的编号。

输出格式
输出一行，为获得两个奖项的人的编号，按在科技创新奖获奖名单中的先后次序输出。

输入输出样例
输入 #1

4 3
2 15 6 8
8 9 2

输出 #1

2 8

说明/提示
对于 60% 的数据，1≤n,m≤1000，获得奖项的人的编号 <2×10^9；

对于 100%100% 的数据，1≤n,m≤10 5 ，获得奖项的人的编号 <2×10^9。

输入数据保证第二行任意两个数不同，第三行任意两个数不同。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cstdio>
#include<math.h>

#include <map>
using namespace std;

int n,m,p;
map<int ,bool> v;
int a[100010];
int b[100010];

int main() {
    
    cin >> n >> m;
    
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    for (int i = 1; i <= m; i++) {
        cin >> b[i];
        v[b[i]] = true;
    }
    for (int i = 1 ;i <= n; i++) {
       if(v[a[i]] ) {
           cout << a[i] << " ";
       }
    }
    
    return 0;
}

好用！！

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cstdio>
#include<math.h>

#include <map>
using namespace std;

int n,m,p;
int a[100010];
int b[100010];

int binary_search(int x) {
    int l = 1, r  = m;
    while(l <= r) {
        int mid = (l+r)>>1;
        if(b[mid] == a[x] ) {
            return 1;
        }
        if(b[mid-1] < a[x] && b[mid+1] > a[x] ) {
        //中间无值
            return 0;
        }
        if(b[mid] > a[x] ) {
            r = mid;
        }
        else {
            l = mid+1;
        }
    }
    return 0;
}

int main() {
    
    cin >> n >> m;
    
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    for (int i = 1; i <= m; i++) {
        cin >> b[i];
    }
    sort(b+1,b+1+m);
    for (int i = 1 ;i <= n; i++) {
       if(binary_search(i) ) {
           cout << a[i] << " ";
       }
    }
    
    return 0;
}

二分