问题 I: 简单查找
时间限制: 3 Sec 内存限制: 22 MB
提交: 688 解决: 123
题目描述
给定一个集合，查找元素是否在集合中出现。
输入
每个测试用例由多行组成，第一行是两个整数n和m，这2个数的取值在1到3 000 000之间。
自第二行起一共有n+m个整数，其中前面n个整数代表集合的元素，随后的m个整数是待查询的数。n+m个整数的取值在范围1到10 000 000之间。
输出
对于每个待查询的数，如果在集合中则输出yes,否则输出no.
样例输入
5 345 56 23 6 56633 66 63 22934 235 555555 230 0
样例输出
no
no
yes
yes
no
思路：快排+二分查找。
#include<stdio.h> #include<algorithm> using namespace std; int a[3333333]; int main() { int n,m,b; while(scanf("%d%d",&n,&m)!=EOF) { if(m==0&&n==0) return 0; int i,j; for(i=0;i<n;i++) scanf("%d",&a[i]); sort(a,a+n); int flag=0; for(j=0;j<m;j++) { flag=0; scanf("%d",&b); int left=0,right=n-1,mid; while(left<=right) { mid=(left+right)/2; if(b==a[mid]) { printf("yes\n"); flag=1; break; } if(b>a[mid]) left=mid+1; else right=mid-1; } if(flag==0) printf("no\n"); } } return 0; }
