この記事は「
アルゴリズムの方法論をつつく3−番兵法。見張り番で効率UP。
」
との連動企画ピヨ。詳しい説明はそちらを見てね。
そして、ボクの実装例を見る前に自分で実装を試みよう。
お待たせ♪それじゃつつくピヨ♪
#include
using namespace std;
//保持するデータの最大数
static const int MAX = 10;
//線形探索法で指定された値を探索する
//なお、戻り値がー1の場合は発見出来なかった事を示す。
class SearchMan {
public:
static int LinearSearch(int target[ MAX + 1], int searchValue) {
int index;
//番兵をしのばす
target[ MAX ] = searchValue;
//逐次的に探す
for( index = 0; target[ index ] != searchValue ; index++) { }
//見つかったの？それとも番兵？
if ( index == MAX ) return -1;
return index;
}
};
int main(void)
{
int values[ MAX + 1 ] = { 9,3,5,6,2,8,7,0,1,4,0 };
//整理前のデータを確認
cout << "整列前のデータを表示します。" << endl;
for(int i = 0; i < MAX; i++) cout << values[i] << '\t';
cout << endl;
//探索するデータを決定
int searchValue = 0;
cout << "検索する数値を0〜9の範囲内で指定して下さい：";
cin >> searchValue;
//線形探索の結果を表示
int index = SearchMan::LinearSearch(values, searchValue );
if ( index == -1 ) {
cout << "指定された値「" << searchValue <<
"」は用意された配列内に存在しません。" << endl;
return -1;
}
cout << "指定された値「" << searchValue << "」を"
<< ( index + 1 ) << "番目で発見しました！" << endl;
return 0;
}
前の実装と見比べてみよう。
逐次的に探すの部分がかなり効率的になっているピヨ。今回は件数が少ないからメリットが見えにくいけど、１００0万件とか大量のデータだったらパフォーマンスに差が出るピヨ。今回はこれでおしまい。次回お楽しみに！
ピッヨッピヨ。