题目

2003年清华大学计算机考研上机

本题不可直接O(n)来搜索，数据量大，千万级别，1s过不去，所以采用二分查找。

代码

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 using namespace std;
 5 
 6 typedef struct student{
 7     char cno[100];
 8     char name[100];
 9     char sex[5];
10     int age;
11 }student;
12 
13 bool cmp(student a,student b){
14     return strcmp(a.cno,b.cno) < 0;
15 }
16 int main(){
17     int n,m;
18     while(scanf("%d",&n)!=EOF){
19         student stu[1000];
20         for(int i = 0;i < n;i++){
21             scanf("%s%s%s%d",stu[i].cno,stu[i].name,stu[i].sex,&stu[i].age);
22         }
23         sort(stu,stu+n,cmp);
24         
25         scanf("%d",&m);
26         while(m--){
27             char x[30];
28             scanf("%s",x);
29             int low = 0, high = n-1;
30             int ans = -1;
31             while(low <= high){
32                 int mid = (low + high) / 2;
33                 if(strcmp(stu[mid].cno,x) == 0 ){
34                     ans = mid;
35                     printf("%s %s %s %d\n",stu[mid].cno,stu[mid].name,stu[mid].sex,stu[mid].age);
36                     break;
37                 }  
38                 if(strcmp(stu[mid].cno,x) < 0) low = mid +1;
39                 if(strcmp(stu[mid].cno,x) > 0) high = mid -1;
40             }
41             if(ans == -1)  printf("No Answer!\n");
42         }
43     }
44     return 0;
45 }