アルゴリズムとプログラミング
基本情報技術者試験 科目A免除 修了試験 20170723 実施分 問6
昇順に整列済みの配列要素 A(1)，A(2)，…，A(n) から，A(m)＝k となる配列要素 A(m) の添字 m を 2 分探索法によって見つける処理を図に示す。終了時点で m＝0 である場合は，A(m)＝k となる要素は存在しない。図中の a に入る式はどれか。ここで，“／”は，小数点以下を切り捨てる除算を表す。
フローチャート: 開始 → [1 → x, n → y] → 判定 x : y。x : y の「>」側 → [0 → m] → 終了。「≦」側 → [a] → 判定 k : A(m)。k : A(m) が「=」→ 終了。「<」→ [m−1 → y] → 判定 x : y の入口へ戻る。「>」→ [m+1 → x] → 判定 x : y の入口へ戻る。
- ア (x+y) → m
- イ (x+y) ／ 2 → m
- ウ (x−y) ／ 2 → m
- エ (y−x) ／ 2 → m
出典：基本情報技術者試験 科目A免除 修了試験 20170723 実施分 問6
答えと解説を見る
正解：イ
覚える知識
2分探索法のフローチャート読解(中央要素の添字)
2分探索では範囲[x,y]の中央(x+y)/2をmとして比較し、範囲を半分に絞る。
この問題で必要なこと
探索範囲x〜yの中央の添字は(x+y)/2(小数点以下切捨て)で求める。
ひっかけ
差(x-y)/2や(y-x)/2を選ばせ、範囲の中央位置とは異なる値にする。
この知識の出題：本試験系 1 回・免除試験 3 回（公開問題での観測値）