ももの知恵の樹

C言語アルゴリズム-線形探索法

線形探索 (Linear Search)とは

線形探索とは、先頭から末尾まで順番に検索対象を比較して探索する方法です。

検索するデータが多くなると遅くなりがちですが、アルゴリズムが単純であり、要素の数が小規模な配列に対してはかえって高速な処理結果となる場合があるため、利用頻度が高い探索方法であると言えます。また、検索対象のデータ構造がどのような条件でも利用できる手軽さが利点となります。


線形探索の性能について

線形探索では、検索データの要素数が増加した分だけ探索に時間がかかります。例えば、要素数1000の配列は、要素数10の配列の100倍の実行時間がかかることとなります。最も処理時間がかかるのは探しているデータが存在しない場合であり、最も時間がかからないのはデータが先頭にあった場合です。


n個のデータからm個のデータを検索する場合、 時間計算量はO(nm)、空間計算量はO(1)必要となります。

データ量と処理時間が単純に比例して増える事を「線形時間」またな「O(n)」と表現します。


C言語による線形探索法プログラム

素数の配列を生成して、配列に対して目的の数値を線形探索します。 


#include <stdio.h>

#define ARRAY_NUM(a) (sizeof(a)/sizeof(a[0]))

/*!
 * @brief       素数の配列を作成する
 * @param[out]  array       数値格納用配列
 * @param[in]   array_size  配列最大要素数
 */
static void
array_prime_number(int *array, unsigned int array_size)
{
    int array_pos = 0; /* 格納先の位置 */
    int tmp = 0;
    int i, j;

    /* 配列を素数で満たす */
    for(i = 1; array_pos < array_size; i++){
        tmp = 0;
        for(j = 1; j <= i; j++){
          if((i % j) == 0) tmp++;
        }

        /* 素数ならば配列に格納する */
        if(tmp == 2){
            array[array_pos] = i;
            array_pos++;
        }
    }
    return;
}

/*!
 * @brief      線形探索を行う
 * @param[in]  array      検索データ配列
 * @param[in]  array_size 配列のサイズ
 * @param[in]  target     検索対象の数値
 * @return     要素の位置。見つからなければ-1を返す。
 */
static int
linear_search(int *array, unsigned int array_size, int target)
{
    int i;

    for(i = 0; i < array_size; i++){
        if(array[i] == target) return(i);
    }

    return(-1);
}

int
main(void)
{
    int rc = 0;
    int num[300];

    /* 素数配列を作成する */
    array_prime_number(num, ARRAY_NUM(num));

    /* 線形探索を行う */
    rc = linear_search(num, ARRAY_NUM(num), 409);
    if(rc > 0) printf("num[%d]=%d\n", rc, num[rc]);

    return(0);
}

関連ページ