アルゴリズムとデータ構造編【探索】 第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 新規作成。



前の章へ

次の章へ

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

Programming Place Plus のトップページへ