NYOJ 86 找球号(一）

这是第一次用的二分，既然前面写了第二次的，觉得有必要写下。

题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=86

注意看题，整数编号i(0<=i<=100000000)，按这种方法肯定超时，想的太简单了。

#include <stdio.h>
static int a[100000001];//**这里数组开的太大，但按题目要求有不能变小**//
int main()
{
	int s,n,t;
	scanf("%d %d",&s,&n);
	while(s--)
	{
		scanf("%d",&t);
		a[t] = 1;
	}
	while (n--)
	{
		scanf("%d",&t);
		if(a[t]==1)
			printf("YES\n");
		else
			printf("NO\n");
	}
	return 0;
}        

晚上去问匡匡，要用二分法。

AC：

#include<stdio.h>
#include<algorithm>
using namespace std;
int a[1000005];
int main()
{
	int n,s,t,i,j;
	scanf("%d %d",&s,&n);
	for(i=0;i<s;i++)
	{
		scanf("%d",&a[i]);
	}
	sort(a,a+s);
	for(i=0;i<n;i++)
	{
		int first=0,last=s,mid,flag=0;//**标记**//
		scanf("%d",&t);
		while(first<=last)//**二分**//
		{
			mid=first+(last-first)/2;
			if(a[mid]==t)
			{
				flag=1;
				break;
			}
			else if(a[mid]<t)
			    first=mid+1;
			else
			    last=mid-1;
		}
			if(flag==1)
				printf("YES\n");
			else
				printf("NO\n");
	}
		return 0;
}