番兵法

番兵法(線形探索の改善)

線形探索アルゴリズムを高速にするための工夫をしたアルゴリズムです

    • 配列の末尾に検索結果(ダミーデータ)をおく

この方法により、データが同じかという比較と、終端まできたかの検査を同一にできます。つまり、

    • (本物かダミーか関わらず)データが見つかったら、ループから抜ける
    • 本物かダミーかの判定は、ループから抜けた後に確認する

といった方法をとります。これにより、ループ内のステップが1つ削減できますので、探索スピードを向上することができます。