二分查找学生信息

落日映苍穹つ 2022-06-01 00:59 161阅读 0赞

*  题目描述

输入 N 个学生的信息，然后进行查询。

*  输入

输入的第一行为 N，即学生的个数(N<=1000)
    接下来的 N 行包括 N 个学生的信息，信息格式如下:
    01 李江 男 21
    02 刘唐 男 23
    03 张军 男 19
    04 王娜 女 19
    然后输入一个 M(M<=10000),接下来会有 M 行，代表 M 次查询，每行输入
    一个学号，格式如下:
    02 
    03 
    01 
    04

*  输出

输出 M 行，每行包括一个对应于查询的学生的信息。 如果没有对应的学生信息，则输出“No Answer!”

*  样例输入

4
    01 李江 男 21
    02 刘唐 男 23
    03 张军 男 19
    04 王娜 女 19
    5 
    02 
    03
    01 
    04 
    03

*  样例输出

02 刘唐 男 23 
    03 张军 男 19 
    01 李江 男 21 
    04 王娜 女 19 
    03 张军 男 19

*  代码

#include <stdio.h>
    
    struct{
        char name[50];
        char sex[30];
        int age;
        int flag;
    }student[1001];
    
    int main(int argc, const char * argv[]) {
        int n;
        while(scanf("%d", &n) != EOF){
            int number;
            for(int i = 0;i < n;i ++){
                scanf("%d", &number);
                scanf("%s%s%d",student[number].name,student[number].sex,&student[number].age);
                student[number].flag = 1;
            }
            int m;
            scanf("%d", &m);
            int a[m];
            for(int i = 0;i < m;i ++){
                scanf("%d", &a[i]);
            }
            /*利用存储方式O(1)遍历
            for(int i = 0;i < m;i ++){
                if(student[a[i]].flag == 1)
                printf("%d %s %s %d\n",a[i],student[a[i]].name,student[a[i]].sex,student[a[i]].age);
                else printf("No Answer!\n");
            }
            */
            for(int i = 0;i < m;i ++){
                int low = 0;
                int high = 1000;
                int mid;
                while(low <= high){
                    mid = (high + low)/2;
                    if(mid == a[i] && student[mid].flag == 1){
                        printf("%d %s %s %d\n",mid,student[mid].name,student[mid].sex,student[mid].age);
                        break;
                    }
                    else if(mid == a[i] && student[mid].flag == 0){
                        printf("No Answer!\n");
                        break;
                    }
                    else if(mid > a[i]) high = mid - 1;
                    else if(mid < a[i]) low = mid + 1;
                }
            }
        }
        return 0;
    }

*  总结

若我们依旧采用每次询问时线性遍历数组来查找是否存在我们需要查找的 元素，那么，该算法的时间复杂度达到了 O(n * m)(查找次数 * 每次查找所 需比较的个数)，而这已经达到了千万数量级，是我们所不愿看到的。于是，我 们只有另找方法来解决该题。
    没错，就是二分查找。为了符合查找空间单调有序的要求，我们首先要对所 有数组元素按照学号关键字升序排列。当数组内各元素已经升序有序时，我们就 可以在每次询问某个特定学号的学生是否存在时，使用二分查找来查找该学生。