番兵を用いた線形探索の最適化

番兵を用いた線形探索の最適化は、列の先頭から順に目的条件を満たす要素を調べる探索法である。

仕組み

各要素を一度ずつ比較し、発見時に位置を返し、末尾までなければ失敗を返す。

計算量・性質

最良O(1)、平均・最悪O(n)、補助領域O(1)。

具体例

[7,4,9]で9を探す場合は3回比較する。

限界と注意点

整列を要求しない一方、大規模入力で繰り返す場合は索引や別構造が有利になる。