<目次>
記事の目的
本記事の目的は以下の通りです。
- 代表的な探索アルゴリズムの一つである「二分探索法」を、Excel VBAでコードを書いて、プログラムを動かすことで理解を深めること。
- 基本情報技術者試験、応用情報技術者試験の試験対策として、「二分探索法」の学習をすること。
二分探索法とは
二分探索法とは、昇順もしくは降順に並んでいる配列に対して、探索範囲を半分に限定しながら目的のデータを探索するアルゴリズムです。
代表的な探索アルゴリズムの一つで、英語では「binary search」(バイナリーサーチ)といいます。
<二分探索法の動き>
目的のデータと配列の中央のデータを比較します。
目的のデータと配列の中央のデータが一致しない場合は、目的のデータと中央のデータの大小関係により、探索範囲を前半、もしくは後半の半分に限定します。(探索範囲を半分に限定するときには、中央のデータを省きます)
この操作を、データが一致するもしくは、探索する範囲がなくなるまで繰り返します。
二分探索法の例
以下の画像の例では、昇順に整列済みの配列Aに対して、二分探索法で「14」を探しています。
＜1回目＞では、探索範囲の中央のA(6)と14を比較します。A(6)が探索データより小さいため、A(0)～A(6)の範囲には探索データがないことが分かります。
＜2回目＞では、lowを「<1回目>のmiddle+1」に切り上げて範囲を限定しています。探索範囲の中央のA(10)と探索データを比較しています。
A(10)が探索データより大きいため、A(10)～A(14)に探索データがないことが分かります。
＜3回目＞では、highを「<2回目のmiddle-1>」に切り下げて範囲を限定しています。探索範囲のA(8)と探索データを比較し、データが一致しているため、探索データ「14」が配列に存在することが分かりました。
二分索法の探索回数、計算量
二分探索法にて、N個のデータから特定のデータを探索する場合の探索回数、計算量は以下の通りです。
| 最小回数 | 1 |
|---|---|
| 最大回数 | (log2N)+1 |
| 平均回数 | log2N |
| 計算量 | O(logN) |
二分探索法をVBAで書いてみる
以下のように1行目に昇順に並んだ数字が入力されてるデータから、特定の数字を二分探索するコードを考えてみましょう。
書き方はいろいろありますが、以下のように書きました。
InputBoxで入力された数字を二分探索し、データがあった場合は何番目に存在したかをメッセージで返すコードとなっています。
※1行目の数字データは、何個でも対応可能です。
※データは昇順に並んでいる必要があります。
Option Explicit Sub binarySearch() '変数の宣言 Dim target As Long Dim low As Long, high As Long, middle As Long Dim result As String '探索する数字を入力 target = InputBox("対象") '結果の初期値を入力 result = target & "は存在しません" 'low、high、middleに列番号(インデックス番号)を格納 low = 1 high = Cells(1, Columns.Count).End(xlToLeft).Column middle = (low + high) / 2 'low > middleになるまで、繰り返す。 Do While low <= high '列番号middleの値で分岐する Select Case Cells(1, middle) 'middle = target なら、resultに結果を格納して、繰り返しを抜ける Case target result = target & "は" & middle & "番目に存在します。" Exit Do 'middle > target ならhighを切り下げる(探索範囲を前半に絞る） Case Is > target high = middle - 1 'middle < target ならlowを切り上げる(探索範囲を後半に絞る) Case Is < target low = middle + 1 End Select '切り下げたhighもしくは切り上げたlowをもとにmiddleを算出 middle = (low + high) / 2 Loop '結果を表示させる MsgBox result End Sub
以上、お読みいただきありがとうございました。
