ZCMU 1099 查找元素2

Description

给定一个整数集合s,集合中有n个元素,我有m次询问,对于每次询问给定一个整数x,若 x存在于集合s中输出x found at y,y为集合s按从小到大排序后第一次出现x的下标,否则输出x not found.

Input

Output

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

先排序，再二分法，代码刚开始有很多bug，后来弄好了，可能不是最简单的，但毕竟原创的。

#include<stdio.h>
#include<stdlib.h>
int cmp(const void *i,const void *j)  
{  if(*(int *)i>*(int *)j) return 1;  else if(* (int *)i==*(int *)j) return 0;  else return -1;  
} 
int main()
{int n,m,i,mi,pan,max,min,t,k=1;while(~scanf("%d%d",&n,&m)){int s[n];t=n;for(i=0;i<n;i++)scanf("%d",&s[i]);qsort(s,n,sizeof(s[0]),cmp);printf("CASE# %d:\n",k);k++;for(i=0;i<m;i++){pan=0;scanf("%d",&mi);if(mi==s[0]){printf("%d found at 1\n",mi);continue;}if(mi==s[1]){printf("%d found at 2\n",mi);continue;}max=t;min=1;n=(t+1)/2;while(max!=min+1){if(mi==s[n]){pan=1;break;}if(mi<s[n])max=n;else min=n;n=(max+min)/2;}while(s[n]==s[n-1])n--;if(pan==1)printf("%d found at %d\n",mi,n+1);else printf("%d not found\n",mi);}}return 0;
}