アルゴリズムとプログラミング
基本情報技術者試験 科目A免除 修了試験 20131215 実施分 問6
昇順に整列された n 個のデータが格納されている配列 A がある。流れ図は，2 分探索法を用いて配列 A からデータ x を探し出す処理を表している。a, b に入る操作の適切な組合せはどれか。ここで，除算の結果は小数点以下が切り捨てられる。
流れ図: 開始 → [1→lo, n→hi] → (ループ先頭) [(lo+hi)/2→k] → 判定 A(k):x。A(k)=x のとき「x は存在する」へ。A(k)<x のとき[a]へ。A(k)>x のとき[b]へ。[a]と[b]の後は合流して判定 lo:hi。lo≦hi のときループ先頭（(lo+hi)/2→k の手前）へ戻る。lo>hi のとき「x は存在しない」へ。「x は存在する」「x は存在しない」はいずれも 終了 へ。
- ア a: k+1→hi，b: k−1→lo
- イ a: k−1→hi，b: k+1→lo
- ウ a: k+1→lo，b: k−1→hi
- エ a: k−1→lo，b: k+1→hi
出典：基本情報技術者試験 科目A免除 修了試験 20131215 実施分 問6
答えと解説を見る
正解：ウ
覚える知識
2分探索法のフローチャート読解(中央要素の添字)
2分探索は中央要素と比較し、探索範囲を半分に絞り込む。
この問題で必要なこと
昇順配列でA(k)<xなら探す範囲は右半分なのでk+1→lo、A(k)>xなら左半分なのでk−1→hiとする。
ひっかけ
loとhiの更新を逆にした組合せ、またはk±1を取り違えたもの。
この知識の出題：本試験系 1 回・免除試験 3 回（公開問題での観測値）