HOME»基本情報技術者平成19年秋期»午前問14
基本情報技術者平成19年秋期 午前問14
問14
昇順に整列されたn個のデータが格納されている配列Aがある。流れ図は，2分探索法を用いて配列Aからデータxを探し出す処理を表している。a，bに入る操作の正しい組合せはどれか。ここで，除算の結果は小数点以下が切り捨てられる。
- [出題歴]
- ソフトウェア開発技術者 H17春期 問11
分類
テクノロジ系 » アルゴリズムとプログラミング » アルゴリズム
正解
ウ
解説
2分探索法は、要素が昇順または降順に整列された集合に対して、探索範囲を1／2に狭めることを繰り返して目的のデータを探索するアルゴリズムです。
2分探索法では目的とする値が与えられると、まず探索範囲の中央に位置する値と目的値を比較します。そして目的値の方が小さければ中央から探索範囲の最後までを、目的値の方が大きければ探索範囲の最初から中央まで探索範囲から除外して、探索範囲を1／2にします。そして再度、新たな探索範囲の中央値と目的値を比較して探索範囲を半分にする、というように同じ操作を再帰的に繰り返します。
a，bの上の条件分岐は、探索範囲の中央に位置する値"A(k)"と探索する値"x"を比較している部分です。aは、A(k)＜x（中央値より探索対象が大きい）の場合の処理で、探索対象はk以下に存在しないので探索範囲の下限値loにk＋1を代入して探索範囲を1／2に狭めます。bは、逆にA(k)＞x（中央値より探索対象が小さい）の場合の処理なので、探索範囲の上限値hiにk－1を代入して探索範囲を1／2に狭めます。
まとめると、
a(A(k)＜x)＝k＋1→lo，
b(A(k)＞x)＝k－1→hi
なので「ウ」が適切な処理です。
2分探索法では目的とする値が与えられると、まず探索範囲の中央に位置する値と目的値を比較します。そして目的値の方が小さければ中央から探索範囲の最後までを、目的値の方が大きければ探索範囲の最初から中央まで探索範囲から除外して、探索範囲を1／2にします。そして再度、新たな探索範囲の中央値と目的値を比較して探索範囲を半分にする、というように同じ操作を再帰的に繰り返します。
a，bの上の条件分岐は、探索範囲の中央に位置する値"A(k)"と探索する値"x"を比較している部分です。aは、A(k)＜x（中央値より探索対象が大きい）の場合の処理で、探索対象はk以下に存在しないので探索範囲の下限値loにk＋1を代入して探索範囲を1／2に狭めます。bは、逆にA(k)＞x（中央値より探索対象が小さい）の場合の処理なので、探索範囲の上限値hiにk－1を代入して探索範囲を1／2に狭めます。
まとめると、
a(A(k)＜x)＝k＋1→lo，
b(A(k)＞x)＝k－1→hi
なので「ウ」が適切な処理です。