平成24年秋期試験問題 午前問6

平成24年秋期試験問題　午前問6

昇順に整列済みの配列要素A(1)，A(2)，…，A(n)から，A(m)＝kとなる配列要素A(m)の添字mを2分探索法によって見つける処理を図に示す。終了時点でm＝0である場合は，A(m)＝kとなる要素は存在しない。図中のaに入る式はどれか。ここで，"／"は，小数点以下を切り捨てる除算を表す。

(x＋y)→m
(x＋y)／2→m
(x－y)／2→m
(y－x)／2→m

正解　イ問題へ

分野：テクノロジ系
中分類：アルゴリズムとプログラミング
小分類：アルゴリズム

解説

2分探索法は、要素が昇順または降順に整列された集合に対し、探索範囲を2分の1に狭めることを繰り返して目的のデータを探索するアルゴリズムです。

2分探索法では目的とする値が与えられると、次の操作を再帰的に繰り返してその値を探索します。

探索範囲の中央に位置する値と目的値を比較する
目的値のほうが小さければ中央から探索範囲の最後までを、目的値のほうが大きければ探索範囲の最初から中央まで探索範囲から除外する（探索範囲が2分の1になる）
1に戻る

流れ図のaの部分は、探索範囲の中央値の添え字をmに代入する処理です。仮に整列済み配列が A[1]～A[11] までの11要素だったとすると、中央値を保持する要素はA[6]となります（m=6）。これは「(1＋11)÷2＝6」という式で求めることができます。xが探索範囲の最小値、yが探索範囲の最大値の添え字を保持しているので、添字を求める式は「(x＋y)／2」が適切です。なお／は小数点以下切捨てなので、配列の要素数が偶数個のときには、中央に位置する2要素のうち添字が小さい要素が選択されます。

具体的にxが1、yが100で探索対象の添字が18の時の流れをトレースしていくと、以下の流れとなります。

(1＋100)／2＝50 → m
50－1＝49 → y
(1＋49)／2＝25
25－1＝24 → y
(1＋24)／2＝12
12＋1＝13 → x
(13＋24)／2＝18
探索対象が見つかったので処理終了

以上のように、2分探索法ではループの度に"x"と"yの中央値"を変えながら目的とする値を探索していきます。