例2.10 查找学生信息 （1069）

题目描述：输入N个学生的信息，然后进行查询。 输入： 输入的第一行为N，即学生的个数(N<=1000)，接下来的N行包括N个学生的信息，然后输入一个M(M<=10000),接下来会有M行，代表M次查询，每行输入一个学号。 输出： 输出M行，每行包括一个对应于查询的学生的信息。如果没有对应的学生信息，则输出“No Answer!”

样例输入：401 李江 男 2102 刘唐 男 2303 张军 男 1904 王娜 女 1950203010403样例输出：02 刘唐 男 2303 张军 男 1901 李江 男 2104 王娜 女 1903 张军 男 19

这道题如果采用线性遍历数组来查找是否存在我们需要的元素，那么该算法的时间复杂度达到了O(n*m)，而这已达到了千万数量级，是我们不愿意看到的。

利用二分查找，原来O(n*m)的时间复杂度被优化到O(nlogn(排序)+mlogn),符合我们的要求。

#include
     
      #include
      
       #include
       
        using namespace std;struct Student{    char name[100];    char sex[5];    int age;    char no[100];    bool operator <(const Student &B)const{        return strcmp(no,B.no)<0;    }}buf[1000];int main(){    int n;    while(scanf("%d",&n)!=EOF){        for(int i=0;i
        
         =base){
   //二分查找                 int mid=(top+base)/2;                int tmp=strcmp(buf[mid].no,x);                if(tmp==0){                    ans=mid;                    break;                }                else if(tmp>0) top=mid-1;                else base=mid+1;             }            if(ans==-1) printf("No Answer!\n");            else printf("%s %s %s %d\n",            buf[ans].no,buf[ans].name,buf[ans].sex,buf[ans].age);         }    }    return 0;}