アルゴリズムとプログラミング番兵法

配列の線形探索における「番兵法（Sentinel Method）」の主な目的はどれか。

ア.探索ループで毎回行う「配列の末尾チェック（境界チェック）」を省くことで、ループの条件判定を半減させる。正解

イ.探索中に配列の要素が変更されないようにロックする保護機構である。

ウ.探索対象の配列をソートして、二分探索を適用できるようにする前処理である。

エ.配列を二分割して再帰的に探索することで、探索時間をO(log n)に短縮する。

解説

番兵法は「最後の門番を自分で立たせる」テクニック。配列の末尾に探したい値を「番兵」として置いておけば、範囲外チェックが不要になりループが速くなります。

なぜアが正解か

通常の線形探索では各ループで2つの条件を確認します。 ① まだ配列の範囲内か（インデックスの境界チェック） ② 目的の値と一致するか（値の比較）番兵法では探索したい値を配列の末尾+1に追加（番兵として設置）します。番兵があるので配列が尽きる前に必ず一致が見つかるため、①の境界チェックが不要になります。結果としてループ内の条件判定が半分になり、定数倍の高速化ができます。

なぜイは間違いか

配列要素の変更を防ぐロック機能はOS・並行プログラミングにおける「ミューテックス（Mutex）」や「セマフォ」の説明です。番兵法は安全機構ではなく、ループ効率化のためのアルゴリズムテクニックです。

なぜウは間違いか

探索対象をソートする前処理はシェルソートや挿入ソートなどの説明です。番兵法はソートとは無関係で、未ソートの配列にそのまま適用できる線形探索の工夫です。

なぜエは間違いか

配列を二分割して再帰的に探索するのは「二分探索（Binary Search）」の説明です。番兵法はあくまで線形探索の最適化手法であり、探索アルゴリズム自体の計算量はO(n)のままです。

出典: AI生成問題（学習用）

← 前の問題

ダイクストラ法（Dijkstra's Algorithm）の制約として正しいものはどれか。

次の問題 →

次の疑似コードを実行したとき、最後に出力される値はどれか。 ``` var x = 10 function foo(): var x = 20 bar() print(x) function bar(): x = 30 foo() ``` ここで、`bar()` 内の `x = 30` はグローバル変数 `x` を変更し、`foo()` 内の `var x` はローカルスコープを生成するものとする。

アルゴリズムとプログラミングの問題を解くこの分野の問題一覧を見る