スピード勝負

アルゴリズムに大切なことは

・わかりやすい

・メモリ使用量が少ない

・速い

・スタイリッシュ＆エレガント←

4つ目要るのか？

そげなことは置いときまして

『100万個のデータに対して、線形探索と二分探索ではどちらが速いのか？』

って問題があるわけですが、まぁ考えるまでもなく二分探索でしょう

データ数n、探索する数mの時、

線形探索の場合はO(nm)

二分探索の場合は、探索前にソートする必要があるのでO(nlogn) + O(mlogn)

ぶっちゃけ、探索数が少ないときは線形探索の方が速いんだよな

探索数が少ないとき、二分探索全体では（ソートする時間） > （探索する時間）だからだろうね

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <windows.h>
#include <mmsystem.h>

const int SEARCH = 500000;

int cmp(const void *a, const void *b)
{
    return *(int*)a - *(int*)b;
}

int main(void)
{
    int *data;
    int search[SEARCH];
    int i, j, count = 0;
    FILE *fp;
    int start, end;

//  for (i = 0;i < 1000000;i++)
//      printf("%d\n", rand()%5000000);
    
    data = (int*)malloc(sizeof(int)*1000000);
    fp = fopen("rand_data.txt", "r");

    srand(10);
    for (i = 0;i < SEARCH;i++)
        search[i] = rand()%5000000;
    for (i = 0;i < 1000000;i++)
        fscanf(fp, "%d", &data[i]);

/*
///////////////////////////////////////////////////

    count = 0;
    start = timeGetTime();
    for (i = 0;i < SEARCH;i++) {
        for (j = 0;j < 1000000;j++) {
            if (search[i] == data[j]) {
                count++;
                break;
            }
        }
    }
    end = timeGetTime();
    printf("liner search\n");
    printf("Match : %d\n", count);
    printf("Time  : %d msec\n", end-start);

///////////////////////////////////////////////////
*/


    start = timeGetTime();
    count = 0;
    qsort(data, 1000000, sizeof(int), cmp);
    for (i = 0;i < SEARCH;i++) {
        if (bsearch(&search[i], data, 1000000, sizeof(int), cmp) != NULL)
            count++;
    }
    end = timeGetTime();
    printf("quick sort + binary search\n");
    printf("Match : %d\n", count);
    printf("Time  : %d msec\n", end-start);

///////////////////////////////////////////////////

    return 0;   
}