探索/線形探索法 - nkym_memo @ ウィキ

線形探索法

データを端から順番にスキャンしながらキーの比較を行う探索法

• int search(int key) キーを入力して、該当のデータを返す関数。見つからない場合は-1を返す。 計算量：O(n)

struct{
	int key;
	int data;
}table[100]

int n;

int search(int key)
{
	int i = 0;

	while(i < n){
		if(table[i].key == key){
			return (table[i].data);
		}
		i++;
	}
	return -1;
}

番兵(sentinel)の利用

keyの終端のキー値を探索するキーにすることで、探索を高速にする。 探索するキーが最後と終端な場合は見つからなかったとして、-1を返す。

int search(int key)
{
	int i = 0;
	table[99].key = key
	
	while(1){
		if(table[i].key == key){
			return (i == 99 ? -1 : table[i].data);
		}
		i++;
	}
}

サンプルプログラム

• 線形探索法サンプル
  

---

参考文献

• 定本 Cプログラマのためのアルゴリズムとデータ構造(近藤 嘉雪,ソフトバンククリエイティブ,1998)
• Cをさらに理解しながら学ぶデータ構造とアルゴリズム(森本 逞,共立出版,2007)