描述

Medusa同学拿到了2组数字，老师请你编程帮他找出，第2组数中的哪些数，在第1组数中出现了，从小到大输出所有满足条件的数。
比如：
第1组数有：8 7 9 8 2 6 3
第2组数有：9 6 8 3 3 2 10
那么应该输出：2 3 3 6 8 9

输入描述

第一行两个整数n和m，分别代表2组数的数量
第二行n个正整数
第三行m个正整数

输出描述

按照要求输出满足条件的数，数与数之间用空格隔开

用例输入 1 

7 7
8 7 9 8 2 6 3
9 6 8 3 3 2 10

用例输出 1 

2 3 3 6 8 9

提示

对于60%的数据1≤n,m≤1000，每个数<=2x109
对于100%的数据1≤n,m≤100000，每个数<=2x109

来源

数组问题 二分

代码

#include <iostream>
#include <cstdio> 
#include <algorithm> 
using namespace std;
int n, m, k;
int a[100005], b[100005], c[100005];
int main () {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
	}
	sort(a+1, a+n+1);
	for (int i = 1; i <= m; i++) {
		scanf("%d", &b[i]);
		int l = 1, r = n;
		while (l <= r) {
			int mid = l + (r - l) / 2;
			if (b[i] > a[mid]) {
				l = mid + 1;
			} else if (b[i] < a[mid]) {
				r = mid - 1;
			} else {
				c[k++] = b[i];
				break;
			}
		}
	}
	sort(c, c+k);
	for (int i = 0; i < k - 1; i++) {
		printf("%d ", c[i]);
	}
	printf("%d", c[k-1]);
    return 0;
}