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

先頭へ戻る

この章の概要

この章の概要です。


線形探索

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

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

配列から探す

まずは、配列(データ構造編 第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;

    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)
{
    size_t i;

    for( i = 0; i < size; ++i ){
        if( array[i] == value ){
            return &array[i];
        }
    }

    return NULL;
}

実行結果:

見つかりました。

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

連結リストから探す

今度は、連結リスト(データ構造編 第3章参照)から、線形探索によって目的の要素を探すプログラムを書いてみます。ここでは、単方向線形リスト(データ構造編 第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;
    PPPSIntSlist p;

    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 );

    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)
{
    PPPSIntSlist p = list;

    while( p != NULL ){
        if( p->value == value ){
            return p;
        }
        p = p->next;
    }

    return NULL;
}

実行結果:

見つかりました。

連結リストの場合は、先頭の要素から始めて、nextポインタをたどっていきます。この動作が、配列における「添字を +1 しながら末尾まで進む」動作と一致します。

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

まとめ

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

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

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

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


練習問題

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

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


解答ページはこちら


参考リンク



更新履歴

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

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

'2012/6/23 コードライブラリのパス変さらに伴い、リンクを修正。

'2012/1/4 連結リスト版の実装に、ppps_int_slist を使うように変更。

'2011/11/5 平均計算量に関する記述を修正。

'2011/10/28 新規作成。



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

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

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

Programming Place Plus のトップページへ


はてなブックマーク Pocket に保存 Twitter でツイート Twitter をフォロー
Facebook でシェア Google+ で共有 LINE で送る rss1.0 取得ボタン RSS
管理者情報 プライバシーポリシー