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