平成24年度 秋期 午前 問6
アルゴリズム
2分探索法に関する問題
昇順に整列済みの配列要素 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〕
＞ のとき → 〔0 → m〕 → （終了）
≦ のとき → 〔 a 〕（←空欄）
→ 〔判定 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
答えと解説を見る
✓ これが正解イ(x＋y)／2→m
解説
中央の添字は両端を足して2で割って求めます。
2分探索法は、探索範囲の中央にある要素を見て、探しているものより大きいか小さいかで範囲を半分に狭めていく方法です。図では、範囲の左端と右端をそれぞれ別の変数がもっており、範囲がまだ尽きていないことを確かめてから、中央の位置を決めています。軸は一つで、空欄に入るのが範囲の中央を指す添字の求め方になっているかどうかです。中央は左端と右端のちょうど真ん中ですから、二つを足して2で割ります。小数点以下は切り捨てられるので、添字は必ず整数になり、しかも左端と右端の間に収まります。求めた位置の値と探し物を比べ、探し物のほうが小さければ右端を1つ手前へ、大きければ左端を1つ先へ動かして、同じ判定に戻ります。
ほかの選択肢はなぜ違うのか
- ア(x＋y)→m：両端を足しただけで2で割っていないので、真ん中ではなく右端よりさらに先の位置を指してしまいます。配列に用意された範囲の外へ出ることもあります。
- ウ(x−y)／2→m：両端の差を半分にした値は、範囲の広さの半分であって位置ではありません。左端が右端以下である間はこの式が0か負の値になり、要素を指せません。
- エ(y−x)／2→m：こちらも範囲の広さを半分にしただけの値です。範囲が右へずれていくと真ん中から離れていくので、位置として使うには左端を足し直す必要があります。
出典：平成24年度 秋期 基本情報技術者試験 午前 問6（改変：原典の図表をテキストに書き起こした）
この解説に誤りを見つけたら教えてください。直して、直した記録を残します。誤りを報告する（メールが開きます）