学生情報の検索-9度チュートリアル第18題

学生情報の検索-9度チュートリアル第18題
タイトル
時間制限:1秒メモリ制限:32メガ特殊判題:Noテーマ記述:N人の学生の情報を入力し、クエリーを行います.入力:入力の第1の行為N、すなわち学生の個数(N<=1000)次のN行はN人の学生の情報を含んで、情報のフォーマットは以下の通りです:01李江男21 02劉唐男23 03張軍男19 04王娜女19それから1つのM(M<=10000)を入力して、次はM行があって、M回のクエリを代表して、各行は1つの学号を入力して、フォーマットは以下の通りです:02 03 01出力:M行を出力して、各行には、クエリーに対応する学生の情報が含まれます.対応する生徒情報がない場合は「No Answer!サンプル入力:4 01李江男21 02劉唐男23 03張軍男19 04王娜女19 5 02 03 03サンプル出力:02劉唐男23 03張軍男19 01李江男21 04王娜女19 03張軍男19出所:2003年清華大学コンピュータ研究生気試験本題
クエリのたびに配列を線形に巡回して、検索する要素が存在するかどうかを検索すると、アルゴリズムの時間的複雑さはO(n*m)(検索回数*検索ごとに比較する必要がある個数)に達し、これはすでに千万桁に達している.

#include 
#include 

struct Student{
    char num[10];
    char name[10];
    char sex[10];
    int age;
};

int main()
{
    int n,m;
    while(scanf("%d",&n)!=EOF){
        Student student[n];
        for(int i=0;i

長さLの秩序配列を二分で検索すると,時間的複雑さは本来線形に検索されたO(L)からO(logL)に低減できる.検索空間の単調な順序付けの要件を満たすために、まずすべての配列要素を学号キーワードの昇順に並べます.配列内の各要素が昇順に整列している場合、特定の学号の学生が存在するかどうかを尋ねるたびに、二分検索を使用して学生を検索できます.

#include 
#include 
#include 

using namespace std;

struct Student{ //            
    char no[100]; //  
    char name[100]; //  
    int age; //  
    char sex[5]; //  
    bool operator < (const Student & A) const { //            sort    
        return strcmp(no,A.no) < 0;
    }
}buf[1000];

int main () {
    int n;
    while (scanf ("%d",&n) != EOF) {
        for (int i = 0;i < n;i ++) {
            scanf ("%s%s%s%d",buf[i].no,buf[i].name,buf[i].sex,&buf[i].age);
        } //  
        sort(buf,buf + n); //               
        int t;
        scanf ("%d",&t); // t   
        while (t -- != 0) { //while         t
            int ans = -1; //      ,    -1
            char x[30];
            scanf ("%s",x); //     
            int top = n - 1,base = 0; //   ，    0,    n-1,         
            while(top >= 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!
");
            }
            else printf("%s %s %s %d
",buf[ans].no,buf[ans].name,buf[ans].sex,buf[ans].age); //     
        }
    }
    return 0;
}

二分検索により,本来のO(n*m)の時間的複雑さはO(nlogn(ソート)+m*logn)に最適化され,この複雑さは要求に合致する.
補足
昇順で整列した配列で、この下句読点の前(下句読点を含む)の数字が目標数字(配列の最小値以上)よりも小さく、配列の残りの部分が目標数字よりも大きく、プログラムをどのように記述するかを決定します.

//           buf,    size,     target
int base = 0 , top = size; //           
while (base <= top) { //             
	int mid = (base + top) / 2;
	if (buf[mid] <= target) base = mid + 1; //          
	else top = mid - 1; //  
}
int ans = top; //  ,top           ,buf[top]