> 探索 > 線形探索法

探索/線形探索法

Last-modified: 2010-07-16 (金) 11:14:39

線形探索法

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

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++;
	}
}