杨杨的游戏
描述
小杨5岁生日那年他爸爸给他买了N（1<N<100000）个球。每个球上都有一个编号i（0<i<232-1），编号可以重复，现在小杨在玩一个游戏。小杨的爸爸随机说出一个数M（0<M<232-1）。需要小杨判断这个数M是否存在N个球的编号中，若小杨答对，就会得到一颗他最喜欢的吃糖。现在小杨拿着这个游戏来考你这ACMer的大神，相信应该难不到你吧。O(∩_∩)O哈哈~。
输入
输入有多个测试数据，每行一个数N，K（1<K<100000），接下来有N个数表示球的编号。接下来会有K个数表示K次查找。
输出
输出YES或者NO
样例输入
6 4 23 34 46 768 343 343 2 4 23 343
样例输出
NO NO YES YES
开始就是一个一个的去查找，然后就是爆表，时间超时很严重。回来看见自己的一个查找方法，二分法查找。就没有超时间了。不过还是时间好多。
C语言代码如下：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int a[100005]; int n; int cmp(int k) { if(a[1]==k || a[n]==k) return 1; int t,max,min; min = 1; max = n; while(min<max){ if(a[max]==k) return 1; else max = max-1; if(a[min]==k) return 1; else min = min+1; t = (max+min)/2; if(a[t]==k) return 1; else { if(a[t]>k && a[min]<k) { max = t-1; } else { if(a[t]<k && a[max]>k) { min = t+1; } } } if(k>a[max] || k<a[min]) return 0; } } int main() { int m; while(scanf("%d%d",&n,&m)!=EOF) { memset(a,0,sizeof(a)); for(int i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+1+n); int k; while(m--){ scanf("%d",&k); if(a[1]>k || a[n]<k) printf("NO\n"); else { if(cmp(k)==1) printf("YES\n"); else printf("NO\n"); } } } return 0; }数据较少的时候，其实我比较喜欢java中的一个函数和链表。
java代码如下：
import java.util.ArrayList; import java.util.Collections; import java.util.Scanner; class test_1 { public static void main(String[] args) { ArrayList<Integer> list = new ArrayList<Integer>(); Scanner sc = new Scanner(System.in); int n; while(sc.hasNext()){ n = sc.nextInt(); int m = sc.nextInt(); for(int i=0;i<n;i++){ int k = sc.nextInt(); list.add(k); } Collections.sort(list); for(int i=0;i<m;i++){ int k = sc.nextInt(); int pc = Collections.binarySearch(list,k); if(pc!=-1) System.out.println("YES"); else System.out.println("NO"); } } } }
数据较大的时候就是超时，估计就是那个自带查找函数耗时间太多了。
解决的方法： （1）重写方法。
（2）自己去写一个方法。
例如：
去重写函数的话。用一个类去实现Collections接口中的函数binarySearch（list，k）。将方法改造为c语言代码一样的查找就可以，具体可以去参照c语言代码！
