UVa 10474 Where is the Marble

本題題目連結
想法：
　　將數列排序好後直接用二分搜尋即可。

	#include <cstdio>
	#include <algorithm>
	using namespace std;
	int N,Q,Case=1;
	int n[10001],q[10001];
	int Search (int q)
	{
	int L=0, R=N-1, mid;
	while (L!=R){
	mid = (L+R)/2;
	if (n[mid] >= q) R = mid;
	else L = mid+1;
	}
	if (n[L] == q) return L+1;
	else return -1;
	}
	int main()
	{
	//freopen ("input.txt","rt",stdin);
	while (scanf("%d%d",&N,&Q)){
	if (!N && !Q) break;
	for (int i=0;i<N;i++) scanf("%d",&n[i]);
	for (int i=0;i<Q;i++) scanf("%d",&q[i]);
	sort (n,n+N);
	printf("CASE# %d:\n",Case++);
	for (int i=0; i<Q; i++){ // q loop
	int position = Search(q[i]);
	if (position == -1) printf("%d not found\n",q[i]);
	else printf("%d found at %d\n",q[i],position);
	}
	}
	return 0;
	}

view raw [UVa] 10474 Where is the Marble.cpp hosted with ❤ by GitHub