番兵とは？ばんぺい
番兵とは、線形探索などで、配列の末尾にあらかじめ探索対象と同じ値を置いておく手法。センチネルともいう。必ず見つかることが保証されるため、繰返しの中で「配列の終端に達したか」の判定を省け、1回あたりの比較回数を減らして高速化できる。
最終更新：2026-10-06
応用情報を最短で暗記・合格する →具体例
100要素の配列の101番目に探索キーと同じ値を入れておくと、ループの条件は「要素がキーと一致するか」だけで済む。見つかった位置が101なら「元のデータには存在しなかった」と判断できる。判定が2つから1つに減るぶん実行時間が短縮される。
試験での引っ掛け
番兵は計算量のオーダー（O(n)）を改善するものではなく、定数倍を減らす工夫にすぎない。「O(n)がO(log n)になる」といった選択肢は誤り。また番兵を置くぶん配列の大きさを1つ多く確保する必要がある。
関連用語
出典・参考
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。