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