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

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

この章の概要

この章の概要です。


線形探索

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

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

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

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

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

配列に対する線形探索

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

#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関数が、線形探索のコードになっています。ほとんど説明することがないくらい簡単だと思います。

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


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

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

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

単方向線形リストの実装は、コードライブラリにあるサンプル実装 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 しながら末尾まで進む」動作です。

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

まとめ

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

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

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

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

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


練習問題

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

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


解答ページはこちら


参考リンク


更新履歴

’2015/12/27 SIZE_OF_ARRAYマクロの定義を修正。

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

≪さらに古い更新履歴を展開する≫



前の章へ (第0章 はじめに)

次の章へ (第2章 線形探索の効率改善)

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

Programming Place Plus のトップページへ



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