番兵付きリニアサーチ

こんにちは、even_ekoです。
今まで、VirtualBoxを使っていたのですが、最近VMWareの凄さに気づいて感動しています。
この感動は、CyberduckからTransmittに変更した時の感動と同じぐらいです。
まぁ、とにかくすごいということです。

今日は、番兵付きリニアサーチについてです。
まずは、通常のリニアサーチを紹介します。
リニアサーチとは、地道に一要素ずつ確認していく処理のことです。

C++で書いた処理が以下になります。
A[] : 探索される配列
n : 配列の要素数
v : 探索している値

int lineaSerarch(int A[],int n,int v){
	int k=0;
	while(k<n){
		if(A[k]==v){
			return k;
		}
		++k;
	}
	return -1;
}

目的の値が見つからなかった場合は-1を返しています。

次に、番兵付きリニアサーチの処理を示します。

int lineaSerarch(vector<int> A,int v){
	int n = (int) A.size();
	A.push_back(v);
	int k=0;
	while(A[k]!=v){
		++k;
	}
	if(k<n){
		return k;
	}
	else {
		return -1;
	}
}

要素の追加が必要なので、vectorを使用しています。
vectorの場合は、サイズを簡単に取得できるので、配列の要素数を引数から外しています。
番兵付きリニアサーチの場合、条件確認(if文)を通る回数が減るので計算量が減ります。
これにより、若干の高速化は図れます。

しかし、番兵を付けることのメリットはこれだけではありません。
番兵を付けることにより、処理を分割することができます。
これにより可読性が向上したり、デバッグがしやすくなったりします。

こういう細かいテクニックは、言語に依らず役立つのでどんどん身につけたいものです。