線形探索と番兵 - 計算機の学習メモ

番兵を使った線形探索の実装。
線形探索は床に並べたトランプと端から確認していき、目的の数を探すような
直感的なアルゴリズム。
当然、計算量はデータ量Nに対してO(N)となる。

しかし、番兵を使うと定数倍の計算量の違いがでる。

番兵を使わないと

for (int i =0; i < n;i++){
    if (A[i] == key) return i+1;
  }

のように、forとifで２回処理が発生する。
一方、番兵を使うと

//番兵をセット
A[n] = key;
while ( A[i] != key ) i++;

のように、処理が１回になる。

したがって、番兵を使わないと2N回の処理が番兵を使うとN回になった。
(現在の計算機ではよほどデータ量が多くないと効果が出にくそうですが・・・。)

ちなみに、何かにつけてif文を使ってしまうため、ループが番兵まで行った時にfalseとするとき、if文を使わずに

return i != n;

とするのは見事だと思う。

■参考資料