線形探索とはなにか？そのアルゴリズムをc++で学ぶ

線形探索とは、配列にような一列に並んだデータを先頭から一つづつ検索していくアルゴリズムのことです。

ランダムに並べられた数列から対象となる数字を検索したい場合は以下のように、
配列の先頭から最後尾まで、目的の数字を探索するプログラムを書きます。

// keyを探すプログラム
int key = 3;
int numbers[] = {2,4,6,8,1,3,5,9,7,10};
for(int i = 0;i < 10;++i){
  if(numbers[i] == key){
    return true;
  }
}

上記のプログラムでは、number[i] == keyにて、
一回のみ条件判定を行なっているように見えますが、
for文でi < 10の条件分岐を判定をしていることから、2回行なっています。
この条件判定を番兵と呼ばれる概念を使用することにより1回に減らすことができます。

番兵とは

データの終了を示すために配置される特殊なデータを指す
wikipediaより

では、データ終了を示すために配置される番兵を使って
線形探索を行なってみます。

データの終了を示すために、Keyとなる数字を配列の末尾に挿入します。 Keyを挿入しているということは、絶対にKeyは見つかります。
配列のindexが末尾まで到達していた場合Keyが見つからなかったことになるので、
この条件を使用することで、2回行われていた判定条件を一つにします。

int key = 3;
// 番兵として配列の末尾にKeyを挿入する
int numbers[] = {2,4,6,8,1,3,5,9,7,10,3};
int i = 0;
while(numbers[i] != key)i++;
// 末尾までいっていたら見つからなかったことになる
return i != 10;

上記のように番兵を使うことで条件分岐の回数を減らすことができました。
ほかの優秀なアルゴリズムがあるので、線形探索自体あまり使われませんが、
有効な考え方だと思いました。