§Algorithm§


☆文字列の探索☆


(逐次探索)


配列の中からあるデータを探し、見つかればその要素番号を返す「探索」 プログラム。逐次探索は下のように先頭要素から順に調べて見つかれば、 そこで処理を中止するという単純な方法です。 数字よりも文字列を探す事の方が多いと思うので、サンプルは文字列が 対象です。


'単純な探索
'SimpleSearch  文字列 target を文字列配列 sdata の中から探し、
'              見つかれば、その要素番号を返す。見つからなければ
'              -1 を返す。sdCount は配列の数
'(文字列の比較は、大文字と小文字の区別をしません)
'(引数には、NULLを指定しないで下さい)
Public Function SimpleSearch(ByVal target As String, _
                             sdata() As String, _
                             ByVal sdCount As Long) As Long
    
    Dim i As Long
    For i = 0& To sdCount - 1&
        If StrComp(sdata(i), target, 1) = 0 Then SimpleSearch = i: Exit Function
    Next i
    SimpleSearch = -1
    
End Function


(3分岐2分探索)


考え方は非線形方程式の解を求める二等分割法と似た感じで、 ソートされた配列に対して、探索データの対象範囲を半分ずつ狭めていく 効率的な方法です。ただ探し出すデータが配列の中に複数存在したとき、 最初に見つかった要素番号を返す所が欠点です。 文字列のソートについては、「ここ」を参考にして下さい。


'3分岐2分探索
'BasicSearch  文字列 target を文字列配列 sdata の中から探し、
'             見つかれば、その要素番号を返す。見つからなければ
'             -1 を返す。sdCount は配列の数
'(文字列の比較は、大文字と小文字の区別をしません)
'(引数には、NULLを指定しないで下さい)
'昇順(ABC順)ソートされた配列データが対象であることに注意して下さい
Public Function BasicSearch(ByVal target As String, _
                            sdata() As String, _
                            ByVal sdCount As Long) As Long
    '探し出す要素の最初と最後と真中の番号
    Dim high As Long, low As Long, mid As Long
    low = 0&: high = sdCount - 1&
    
    Do While (low <= high)
        mid = (low + high) \ 2
        Select Case StrComp(sdata(mid), target, 1)
            Case -1
                low = mid + 1&
            Case 1
                high = mid - 1&
            Case 0
                BasicSearch = mid: Exit Function
        End Select
    Loop
    BasicSearch = -1&
    
End Function


(2分岐2分探索)


3分岐と違い、探し出すデータが配列の中に複数存在したときでも必ず先頭の 要素番号を返します。一見、効率的に見えますが、「low >= high」になるまで 検索を続ける上、ロジックがわかりにくいので、必ずしも万能な検索とはいえません。 ソートされた配列が対象です。


'2分岐2分探索-改
'Basic2Search  文字列 target を文字列配列 sdata の中から探し、
'              見つかれば、その要素番号を返す。見つからなければ
'              -1 を返す。sdCount は配列の数
'              配列内にtargetと一致するものが複数ある時は、必ず
'              先頭の要素番号を返す。
'(文字列の比較は、大文字と小文字の区別をしません)
'(引数には、NULLを指定しないで下さい)
'昇順(ABC順)ソートされた配列データが対象であることに注意して下さい
Public Function Basic2Search(ByVal target As String, _
                             sdata() As String, _
                             ByVal sdCount As Long) As Long
    
    Dim high As Long, low As Long, mid As Long
    low = 0&: high = sdCount - 1&
    
    Do While (low < high)
        mid = (high + low) \ 2&
        If StrComp(sdata(mid), target, 1) = -1 Then
            low = mid + 1&
        Else
            high = mid
        End If
    Loop
    If StrComp(sdata(low), target, 1) = 0 Then
        Basic2Search = low
    Else
        Basic2Search = -1&
    End If
    
End Function


(3分岐2分探索−改)


探し出すデータが配列の中に複数存在したときでも必ず先頭の 要素番号を返します。ここで紹介した物の中では一番利用しやすいかな・・・。 ソートされた配列が対象です。

'3分岐2分探索-改
'BasicSearchEx  文字列 target を文字列配列 sdata の中から探し、
'               見つかれば、その要素番号を返す。見つからなければ
'               -1 を返す。sdCount は配列の数
'               配列内にtargetと一致するものが複数ある時は、必ず
'               先頭の要素番号を返す。
'(文字列の比較は、大文字と小文字の区別をしません)
'(引数には、NULLを指定しないで下さい)
'昇順(ABC順)ソートされた配列データが対象であることに注意して下さい
Public Function BasicSearchEx(ByVal target As String, _
                              sdata() As String, _
                              ByVal sdCount As Long) As Long
    
    Dim high As Long, low As Long, mid As Long
    low = 0&: high = sdCount - 1&
    
    Do While (low <= high)
        mid = (high + low) \ 2
        Select Case StrComp(sdata(mid), target, 1)
            Case 1
                high = mid - 1&
            Case -1
                low = mid + 1&
            Case 0
                Do While (mid > 0&)
                    If (StrComp(sdata(mid), sdata(mid - 1), 1) <> 0) Then Exit Do
                    mid = mid - 1&
                Loop
                BasicSearchEx = mid: Exit Function
        End Select
    Loop
    BasicSearchEx = -1&
    
End Function


(参考書)

『アルゴリズムとデータ構造』
江村潤朗、上坂吉則、浅井宗海、有澤誠、西村俊介
実教出版


(サンプルプログラムの動作確認)

機種 PC-9821V13S
OS Windows95
開発ツール Visual Basic Ver.4.0
更新日 00/11/25

ダウンロード Search.lzh(3.33KB)

Visual Basic Ver.5.0,Ver.6.0でも問題なく動作すると思います。
なお、このコーナーに掲載されているプログラムコード、およびプログラムファ イルが原因で生じた損害などに関して一切の責任を負うことはできません。

★こちらは従来通り、掲載されているプログラムコード、およびプログラムファ イルを無断で配布・転載することは、原則として禁止です。


Algorithmインデックス トップ


Copyright(C)2000 Tomoya. All rights reserved.