Zcmu--1099: find Element II

Description

 Given a set of integers s, There are n Elements , I have a m Time to ask , Give an integer for each query x, if  x Exists in the set s Medium output x found at y,y For collection s It appears for the first time after sorting from small to large x The subscript , Otherwise output x not found.

Input

Multiple sets of test data , The first line of each group is two positive integers n,m.(1<=n,m<=1000) Represents the number of elements in the set and the number of queries , Next n Each row has a positive integer representing the elements in the set .( The size of each integer is less than or equal to 100000), Next m Each row has a positive integer representing the element of the query .

Sample Input

4  1

2

3

5

1 

5

5  2

1

3

3

3

1

2

3

Sample Output

CASE# 1:

5 found at 4

CASE# 2:

2 not found

3 found at 3

analysis ： After sorting, use two points to find The first is greater than or equal to Enter the array subscript of the element , Then compare whether it is the same , The same is to find , Either or the element does not exist .

#include <stdio.h>
#include <algorithm>
using namespace std;
int a[1005];
int main()
{
	int n,q,i,c=1,l,z,mid,y;
	while(~scanf("%d%d",&n,&q)){
		for(i=0;i<n;i++) scanf("%d",&a[i]);
		sort(a,a+n);
		printf("CASE# %d:\n",c++);	// Test case number 
		while(q--){
			scanf("%d",&l);
			z=0,y=n-1;
			while(z<y){		// Binary small core 
				mid=(z+y)/2;
				if(a[mid]>=l) y=mid;
				else z=mid+1;
			}
			if(a[(z+y)/2]==l) printf("%d found at %d\n",l,y+1);// Equality is finding 
			else printf("%d not found\n",l);
		}
	}
	return 0;
}