[VBA]二分検索(Binary serarch)の実装

2020年5月4日

概要

VBAで二分検索を実装しました。O記法での平均計算量はO(log n)です。二分検索はソート済みのランダムアクセス可能なデータ構造にのみ適用可能なアルゴリズムで、今回は一次元配列内を二分検索する実装にしました。戻り値は発見した要素の位置(=添え字 = インデックス)となっています。なお、配列の要素に重複があることを想定し、要素の先頭位置を返すパターンと、要素の末尾の位置を返すパターンで2種類の関数を用意しました。検索値が見つからなかった場合、要素の先頭位置を返す関数は、検索値未満の最大値に対応する位置の補数を返します。要素の末尾位置を返す関数は、検索値を超える最小値に対応する位置の補数を返します。補数の意味が分からない方は、とりあえず整数をNot演算したものと覚えておいて下さい。0以上の整数をNot演算すると、その結果は-1以下となるため、戻り値が-1以下か0以上かを判定することで、検索値が見つかったかどうかを判断できます。また、VBAにおいては、戻り値を格納した変数をResultIndexとした時、「ResultIndex = Not ResultIndex」とすることで、配列要素の位置に変換することができます。

アルゴリズム

基本手順

  1. 配列の検索範囲を2つの添え字(インデックス)で指定する。これらの名前を開始位置(StartIndex)と終了位置(EndIndex)と記載する。検索開始時の開始位置は配列の最小インデックス、終了位置は配列の最大インデックスとする。
  2. 開始位置と終了位置の中間位置(MiddleIndex)を算出する。
  3. 中間位置の要素(評価値)と検索値を比較する。
  4. 検索値より評価値の方が大きい場合、終了位置を(中間位置 – 1)に置き換えて 手順1.に戻る。
  5. 検索値より評価値の方が小さい場合、開始位置を(中間位置 + 1)に置き換えて手順1.に戻る。
  6. 検索値と評価値が同じ場合、中間位置を返して終了する。

先頭のインデックスを取得する手順

配列に重複を許可している場合、すなわち配列内に同じ値が複数含まれている可能性がある場合、基本手順では戻り値のインデックスの位置を保証しません。例えば、{1,2,2,2,3,4,5,6,7,8}というソート済み配列に対して、「2」を検索値として二分検索した場合、配列内に存在する3つ「2」の内、どの要素の位置を返すかは、実装に依存してしてしまいます。例えば新しい要素の挿入位置を二分検索する場合、どの位置が返ってくるかは仕様として定めておきたいですね。そのため、まずは先頭の要素のインデックスを返すアルゴリズムを考えます。下記の手順のグレーマーカー部は基本手順と同一です。

  1. 配列の検索範囲を2つの添え字(インデックス)で指定する。これらの名前を開始位置(StartIndex)と終了位置(EndIndex)と記載する。検索開始時の開始位置は配列の最小インデックス、終了位置は配列の最大インデックスとする。
  2. 開始位置と終了位置の中間位置(MiddleIndex)を算出する。
  3. 中間位置の要素(評価値)と検索値を比較する。
  4. 検索値より評価値の方が大きい場合、終了位置を(中間位置 – 1)に置き換えて 手順1.に戻る。
  5. 検索値より評価値の方が小さい場合、開始位置を(中間位置 + 1)に置き換えて手順1.に戻る。
  6. 検索値と評価値が同じ場合、現在の中間位置を戻り値の候補として保持しておき、
    終了位置を(中間位置 – 1)に置き換えて 手順1.に戻る。

末尾のインデックスを取得する手順

先程と同様の理由で、末尾の要素のインデックスを返すアルゴリズムを考えます。下記の手順のグレーマーカー部は基本手順と同一です。

  1. 配列の検索範囲を2つの添え字(インデックス)で指定する。これらの名前を開始位置(StartIndex)と終了位置(EndIndex)と記載する。検索開始時の開始位置は配列の最小インデックス、終了位置は配列の最大インデックスとする。
  2. 開始位置と終了位置の中間位置(MiddleIndex)を算出する。
  3. 中間位置の要素(評価値)と検索値を比較する。
  4. 検索値より評価値の方が大きい場合、終了位置を(中間位置 – 1)に置き換えて 手順1.に戻る。
  5. 検索値より評価値の方が小さい場合、開始位置を(中間位置 + 1)に置き換えて手順1.に戻る。
  6. 検索値と評価値が同じ場合、現在の中間位置を戻り値の候補として保持しておき、
    開始位置を(中間位置 + 1)に置き換えて 手順1.に戻る。

コード

'* @fn Public Function BinarySearch(ByRef SortedArray As Variant, ByRef Target As Variant, Optional ByVal StartIndex As Long = -1, Optional ByVal EndIndex As Long = -1) As Long
'* @brief ソート済み一次元配列を二分検索(バイナリサーチ)し、検索値と一致する先頭の位置を返します。
'* @param[in] SortedArray 値型のソート済み一次元配列を指定します。内部処理形式が値型のVariant型配列も指定可能です。
'* @param[in] Target 検索値を指定します。
'* @param[in] StartIndex 第1引数SortedArrayの中から、検索する範囲の開始位置をインデックスで指定します。引数を省略するか、-1以下を指定すると、配列の先頭が開始位置となります。
'* @param[in] EndIndex 第1引数SortedArrayの中から、検索する範囲の終了位置をインデックスで指定します。引数を省略するか、-1以下を指定すると、配列の末尾が終了位置となります。
'* @details 計算量はO(log n)です。
'* @return Long 検索値が存在する配列のインデックスを返します。一致する値が存在しない場合、指定した値未満の最大値に対応する位置の補数を返します。
'*
Public Function BinarySearch(ByRef SortedArray As Variant, ByRef Target As Variant, Optional ByVal StartIndex As Long = -1, Optional ByVal EndIndex As Long = -1) As Long
        
    If (StartIndex <= -1) Then StartIndex = LBound(SortedArray)
    If (EndIndex <= -1) Then EndIndex = UBound(SortedArray)
    
    Dim MiddleIndex As Long
    Do While (StartIndex <= EndIndex)
        
        MiddleIndex = StartIndex + (EndIndex - StartIndex) / 2
        If (Target < SortedArray(MiddleIndex)) Then
            EndIndex = MiddleIndex - 1
            
        ElseIf (Target > SortedArray(MiddleIndex)) Then
            StartIndex = MiddleIndex + 1
        
        Else
            BinarySearch = MiddleIndex
            EndIndex = MiddleIndex - 1
        End If
    Loop
    
    If (BinarySearch = 0) Then
        If (Target < SortedArray(MiddleIndex)) Then MiddleIndex = MiddleIndex - 1
        BinarySearch = Not MiddleIndex
    End If
    
    Exit Function
End Function
'* @fn Public Function BinarySearchL(ByRef SortedArray As Variant, ByRef Target As Variant, Optional ByVal StartIndex As Long = -1, Optional ByVal EndIndex As Long = -1) As Long
'* @brief ソート済み一次元配列を二分検索(バイナリサーチ)し、検索値と一致する末尾の位置を返します。
'* @param[in] SortedArray 値型のソート済み一次元配列を指定します。内部処理形式が値型のVariant型配列も指定可能です。
'* @param[in] Target 検索値を指定します。
'* @param[in] StartIndex 第1引数SortedArrayの中から、検索する範囲の開始位置をインデックスで指定します。引数を省略するか、-1以下を指定すると、配列の先頭が開始位置となります。
'* @param[in] EndIndex 第1引数SortedArrayの中から、検索する範囲の終了位置をインデックスで指定します。引数を省略するか、-1以下を指定すると、配列の末尾が終了位置となります。
'* @details 計算量はO(log n)です。
'* @return Long 検索値が存在する配列のインデックスを返します。一致する値が存在しない場合、指定した値を超える最小値に対応する位置の補数を返します。
'*
Public Function BinarySearchL(ByRef SortedArray As Variant, ByRef Target As Variant, Optional ByVal StartIndex As Long = -1, Optional ByVal EndIndex As Long = -1) As Long
    
    If (StartIndex <= -1) Then StartIndex = LBound(SortedArray)
    If (EndIndex <= -1) Then EndIndex = UBound(SortedArray)
    
    Dim MiddleIndex As Long
    Do While (StartIndex <= EndIndex)
        
        MiddleIndex = StartIndex + (EndIndex - StartIndex) / 2
        If (Target < SortedArray(MiddleIndex)) Then
            EndIndex = MiddleIndex - 1
            
        ElseIf (Target > SortedArray(MiddleIndex)) Then
            StartIndex = MiddleIndex + 1
        
        Else
            BinarySearchL = MiddleIndex
            StartIndex = MiddleIndex + 1
        End If
    Loop
        
    If (BinarySearchL = 0) Then
        If (Target > SortedArray(MiddleIndex)) Then MiddleIndex = MiddleIndex + 1
        BinarySearchL = Not MiddleIndex
    End If
        
    Exit Function
End Function

ソースコードの利用について

本ソースコードは「GPL v3.0(GNU General Public License Version 3.0)」ライセンスで利用可能です。

本ソースコードを私的に利用される方は、本ソースコードが無料で利用できると考えて差し支え御座いません。下記の著作権表示をソースコード内に表示して頂ければ幸いです。

Copyright © 2017 黒い箱の中 All Rights Reserved.(https://kuroihako.com/)

本ホームページのソースコードを利用したソフトウェアを商用利用したり、ホームページ等で一般公開する方は、本ホームページのソフトウェアまたはソースコードに適用されているライセンスをご理解頂いてからご使用ください。同ライセンス以外での利用をご希望の方はお問い合わせフォームよりご連絡下さい。