基本情報技術者 試験情報＆徹底解説 -新制度に完全対応-

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

2分探索法では目的とする値が与えられると、まず探索範囲の中央に位置する値と目的値を比較します。そして目的値の方が小さければ中央から探索範囲の最後までを、目的値の方が大きければ探索範囲の最初から中央まで探索範囲から除外して、探索範囲を1／2にします。そして再度、新たな探索範囲の中央値と目的値を比較して探索範囲を半分にする、というように同じ操作を再帰的に繰り返します。

流れ図の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. (1＋100)／2＝50→m
2. 50－1＝49→y
3. (1＋49)／2＝25
4. 25－1＝24→y
5. (1＋24)／2＝12
6. 12＋1＝13→x
7. (13＋24)／2＝18
8. 探索対象が見つかったので処理終了

というように2分探索法ではループの度にxとyの中央値を変えながら対象を探索していきます。