線形探索 | Programming Place Plus　アルゴリズムとデータ構造編【探索アルゴリズム】　第１章

トップページ – アルゴリズムとデータ構造編

この章の概要 🔗

この章の概要です。


線形探索 🔗

最初に紹介する探索アルゴリズムは、線形探索（逐次探索、リニアサーチ）です。

線形探索のアルゴリズムは非常に単純で、データの集まりを先頭から末尾へ向かって、１つずつ順番に探すだけです。

ある意味、工夫がないアルゴリズムなので、あまり速くはありません。とはいえ、計算量は O(n) であり、極端に悪いわけでもありません。

線形探索は、“データを１つずつ順番に” アクセスできるのなら、いつでも使えるアルゴリズムです。配列はもちろんのこと、連結リスト（【データ構造】第３章）でも使えますし、木構造（【データ構造】第７章）でも可能です。

しかし、配列なら二分探索などが使えますし、木構造は二分探索木（【データ構造】第８章などの工夫によって、もっと効率よく探索を行うことができます。

配列に対する線形探索 🔗

まずは、配列（【データ構造】第１章）の中から、目的の値をもった要素を探す処理を、線形探索を使って書いてみます。

#include <stdio.h>

#define SIZE_OF_ARRAY(array)    (sizeof(array)/sizeof(array[0]))

static int* linear_search(int* array, size_t size, int value);

int main(void)
{
    int array[] = { 5, 12, 7, -8, -3, 9 };

    int* p = linear_search( array, SIZE_OF_ARRAY(array), 7 );
    if( p == NULL ){
        puts( "見つかりませんでした。" );
    }
    else{
        puts( "見つかりました。" );
    }

    return 0;
}

/*
    線形探索
*/
int* linear_search(int* array, size_t size, int value)
{
    for( size_t i = 0; i < size; ++i ){
        if( array[i] == value ){
            return &array[i];
        }
    }

    return NULL;
}

実行結果：

見つかりました。

linear_search関数が、線形探索のコードになっています。ほとんど説明することがないくらい簡単だと思います。

戻り値は、発見した要素へのポインタにしています。見つからなかった場合はヌルポインタを返します。


連結リストに対する線形探索 🔗

今度は、連結リスト（【データ構造】第３章）から目的の値をもった要素を探すプログラムを、線形探索を使って書いてみます。

連結リストには、双方向に要素を辿れるタイプや、先頭と末尾で循環しているタイプがありますが、線形探索を使うには、単方向で循環しないタイプ（単方向線形リスト）で十分です。

単方向線形リストの実装は、コードライブラリにあるサンプル実装 ppps_int_slistを使います。

#include <stdio.h>
#include "ppps_int_slist.h"

static PPPSIntSlist linear_search(PPPSIntSlist list, int value);

int main(void)
{
    PPPSIntSlist list = ppps_int_slist_create();

    ppps_int_slist_add_tail( list, 5 );
    ppps_int_slist_add_tail( list, 12 );
    ppps_int_slist_add_tail( list, 7 );
    ppps_int_slist_add_tail( list, -8 );
    ppps_int_slist_add_tail( list, -3 );
    ppps_int_slist_add_tail( list, 9 );

    PPPSIntSlist  p = linear_search( list, 7 );
    if( p == NULL ){
        puts( "見つかりませんでした。" );
    }
    else{
        puts( "見つかりました。" );
    }

    ppps_int_slist_delete( list );

    return 0;
}

/*
    線形探索
*/
PPPSIntSlist linear_search(PPPSIntSlist list, int value)
{
    for( PPPSIntSlist p = list->next; p != NULL; p = p->next ){
        if( p->value == value ){
            return p;
        }
    }

    return NULL;
}

実行結果：

見つかりました。

連結リストに対して線形探索を使うには、先頭の要素から始めて、nextポインタをたどっていきます。この動作は、配列でいえば「添字を 0 から始めて、+1 しながら末尾まで進む」動作です。

連結リストが循環するタイプ（【データ構造】第４章）であったとしても、考え方を変える必要はありません。何らかの方法で、最後の要素まで行き着いたことを検出する必要はありますが、することは同じです。

まとめ 🔗

線形探索は、もっとも実装が容易な探索アルゴリズムです。

線形探索を適用するためには、対象のデータ構造が、すべての要素を漏れなくたどれることが条件になります。

線形探索は、データの個数に比例して処理時間がかかるのは明らかでしょう。対象のデータが 100個なら最大で 100回の比較が行われます。1000個なら最大で 1000回、10000個なら最大で 10000回の比較が必要です。計算量（【導入】第１章）で表現すれば、O(n)です。

なお、比較の最小回数は 1回（目的の要素が先頭にあったとき）ですから、平均的には n/2回の比較が行われます。O記法においては、定数の部分は排除するので、平均的にも O(n) です。

つねに使えるとは限りませんが、線形探索の効率を多少改善する方法があります。次の章で取り上げます。


練習問題 🔗

問題①　最初に見つけた要素ではなく、最後に見つけた要素を返すような linear_search関数を作成してください。

問題②　要素の値ではなく、「偶数」とか「3 の倍数」のような条件で探索できる inear_search関数を作成してください。


解答ページはこちら。


参考リンク 🔗


更新履歴 🔗

　SIZE_OF_ARRAYマクロの定義を修正。

　サンプルプログラムで、ファイルスコープでよい関数に static を付加。

≪さらに古い更新履歴≫

　コードライブラリのパス変更に伴い、リンクを修正。

　連結リスト版の実装に、ppps_int_slist を使うように変更。

　平均計算量に関する記述を修正。

　新規作成。


前の章へ　（第０章　はじめに）

次の章へ　（第２章　線形探索の効率改善）

アルゴリズムとデータ構造編のトップページへ

Programming Place Plus のトップページへ

はてなブックマーク に保存 Pocket に保存 Facebook でシェア
X で ポスト／フォロー LINE で送る noteで書く
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー
先頭へ戻る