VBA Advance8

第8章　バイナリサーチ

リニアサーチはデータ件数が増えるにしたがって遅くなりますが、バイナリサーチはデータ量が増えても遅くはなりません。大量データを検索するときに使用します。

バイナリサーチを行う場合は、検索する表のデータが昇順に並んでいる必要があります。そのため正しい結果を返すために、バイナリサーチの前に表を並び替えます。表が昇順に並んでいることで、順番の中央を比較して大小判断をしながら検索値を見つけます。

この方法で検索をすると、10000件のデータなら平均で13件目で見つかります。見つからない場合でも14件探すだけです。100000件になっても平均で16件目で、最大17件の比較で済みます。

ちなみにVlookup関数の引数がtrueはバイナリサーチになります。Vlookup関数の引数がtrueはデータ量が多くなっても遅くなりません。

バイナリサーチのアルゴリズム

同じブックにあるSheet2のシートの表のA列に該当するC列を取得する、リニアサーチで求める方法（検索値はsDataとする）

Dim ws As Worksheet

Dim imin As Long

Dim imax As Long

Dim icenter As Long

Dim result As Variant

Set ws = ThisWorkbook.Sheets("Sheet2")

'並び替えの処理

ws.Range("A1").CurrentRegion _

.Sort Key1:=Range("A1"), order1:=xlAscending, Header:=xlYes

ws.Sort.SortFields.Clear

result = ""

imin = 2

imax = ws.Cells(Rows.Count, 1).End(xlup).Row

Do While imin <= imax

icenter = (imin + imax) / 2

If sData = ws.Cells(icenter, 1) then

result = ws.Cells(icenter, 3)

Exit Do

ElseIf sData < ws.Cells(icenter, 1) then

imax = icenter - 1

Else

imin = icenter + 1

End If

Loop

icenterが中央値を表す指標で中央値と検索値が同じだったら見つかったものとします。中央値よりも検索値が小さかったらimaxにicenterの指標から1引いたものをセットし、中央値よりも検索値が大きかったらiminにicenterの指標から1足したものをセットします。

このようにすると、対象範囲が徐々に狭まるため、高速に見つけることができます。