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

コード

' [VBA]二分検索(Binary serarch)の実装 
' Copyright (c) 2020-2024  黒箱 
' This software is released under the MIT License;. 
' このソフトウェアはMITライセンスの下でリリースされています。 

'* @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&#91;in&#93; SortedArray 値型のソート済み一次元配列を指定します。内部処理形式が値型のVariant型配列も指定可能です。
'* @param&#91;in&#93; Target 検索値を指定します。
'* @param&#91;in&#93; StartIndex 第1引数SortedArrayの中から、検索する範囲の開始位置をインデックスで指定します。引数を省略するか、-1以下を指定すると、配列の先頭が開始位置となります。
'* @param&#91;in&#93; 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