番兵法とは？
番兵法とは、線形探索で、配列の末尾に探索したい値そのもの（番兵、sentinel）をあらかじめ置いておく工夫。必ずどこかで一致するため、ループ内の「配列の終端を超えたか」の判定が不要になり、比較回数がおよそ半分に減る。見つかった位置が番兵の位置なら「データ中には無い」と判断する。
ばんぺいほう
番兵法の意味
線形探索で、配列の末尾に探索したい値そのもの（番兵、sentinel）をあらかじめ置いておく工夫。必ずどこかで一致するため、ループ内の「配列の終端を超えたか」の判定が不要になり、比較回数がおよそ半分に減る。見つかった位置が番兵の位置なら「データ中には無い」と判断する。
番兵法の具体例
要素数100の配列の101番目に探索値を入れておく。通常なら「i≦100か」と「a[i]＝探索値か」の2つを毎回判定するが、番兵があれば後者だけでよい。100件全て走査しても止まらずに番兵で必ず終わる。
番兵法は試験でどう引っ掛けられる？
番兵は処理を高速化するがオーダーは変わらずO(n)のまま。また番兵用に配列を1つ多く確保しておく必要があり、確保を忘れると領域外アクセスになる。二分探索には使えない。
番兵法と関連する用語
最終更新：2026-08-25／解説は資格暗記が独自に作成しています。 過去問の出典は各問題に記載のとおりです。