修了試験 2013-12-15実施分 基本情報技術者試験 問6

解説

正解は3です。 2分探索法は、整列済みの配列の中央の要素と探す値xを比べ、探索範囲を半分ずつに狭める方法です。 流れ図では、最初にloを1、hiをnとし、中央の位置kを(lo＋hi)/2で求めています。 A(k)とxを比べて「＝」なら見つかったことになり、「＜」ならa、「＞」ならbを実行します。 その後、lo≦hiなら繰り返し、lo＞hiになれば「xは存在しない」として終了します。 【解法の流れ】 A(k)＜xのとき、xはA(k)より大きいので、kより後ろの位置にあります。 このため、探索範囲の下限loをk＋1に変更します。 これがaの処理です。 A(k)＞xのとき、xはA(k)より小さいので、kより前の位置にあります。 このため、探索範囲の上限hiをk－1に変更します。 これがbの処理です。 【選択肢別解説】 1：× aでhiをk＋1にすると、範囲が後ろに進まず、xより小さい要素側を探し続けてしまいます。 bでloをk－1にするのも逆向きで、正しく探索できません。 2：× aでhiをk－1にすると、xがあるはずの後ろ側を探索範囲から外してしまいます。 bでloをk＋1にするのも同じく逆で、xを見つけられません。 3：○ aでloをk＋1に、bでhiをk－1にすると、xがあり得る側だけに範囲を絞れます。 範囲が空になればlo＞hiとなり、正しく終了します。 4：× aでloをk－1にすると、すでに調べたkを含む範囲が残り、範囲が狭まらないことがあります。 bでhiをk＋1にするのも、範囲が縮まず無限ループの原因になります。 【ポイント】 2分探索では、中央の値より探す値が大きければ下限を中央＋1に、小さければ上限を中央－1にします。 中央の位置そのものは調べ終わっているので、範囲から外すために±1します。