アルゴリズムとプログラミング
平成24年度 秋期 基本情報技術者試験 午前 問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] → 終了
- x:y が「≦」→ [a] → 判定 k:A(m)
- k:A(m) が「=」→ 終了
- k:A(m) が「<」→ [m−1 → y] → 判定 x:y に戻る
- k:A(m) が「>」→ [m+1 → x] → 判定 x:y に戻る
- ア (x+y) → m
- イ (x+y)／2 → m
- ウ (x−y)／2 → m
- エ (y−x)／2 → m
出典：平成24年度 秋期 基本情報技術者試験 午前 問6
答えと解説を見る
正解：イ
覚える知識
2分探索法のフローチャート読解(中央要素の添字)
2分探索は探索範囲の中央要素と探索値を比較し、範囲を半分ずつに絞る。
この問題で必要なこと
2分探索では探索範囲の下限xと上限yの中央を(x+y)/2で求め、小数点以下は切り捨てる。
ひっかけ
差(x−y)や和(x+y)をそのまま添字にする誤りを誘う。
この知識の出題：本試験系 1 回・免除試験 3 回（公開問題での観測値）