【探索アルゴリズム】線形探索法とは。Excel VBAで線形探索法を試してみる (基本情報技術者・応用情報技術者試験)

<目次>

記事の目的
線形探索法とは
- 線形探索法の探索回数、計算量
線形探索法をVBAで書いてみる

記事の目的

本記事の目的は以下の通りです。

代表的な探索アルゴリズムの一つである「線形探索法」を、Excel VBAでコードを書いて、プログラムを動かすことで理解を深めること。
基本情報技術者試験、応用情報技術者試験の試験対策として、「線形探索法」の学習をすること。

線形探索法とは

線形探索法とは、配列の先頭の要素から順番に目的の要素を探索していくアルゴリズムです。
代表的な探索アルゴリズムの一つで、英語では「linear search」(リニアサーチ)といいます。

以下の画像では、配列Aから4を線形探索しています。

線形探索法の探索回数、計算量

線形探索法にて、N個のデータから特定のデータを探索する場合の探索回数、計算量は、以下表のとおりです。

最小回数	1
最大回数	N
平均回数	(1+N)÷2
計算量	O(N)

探索回数は、一番最初に探索するデータがある場合が最小の1回、N番目に探索するデータがある場合が最大のN回です。
そのため、線形探索法の平均探索回数は、( 1 + N ) ÷ 2です。
〈(最小探索回数1回+最大探索回数N回) ÷ 2回〉

線形探索法をVBAで書いてみる

以下のように[A1]～[E1]の5つの数字から、特定の数字を線形探索するコードを考えてみましょう。

書き方はいろいろありますが、以下のように書きました。
InputBoxで入力された数字を線形探索し、データがあった場合は何番目にあったかをメッセージで返すコードとなっています。

Option Explicit
'配列のインデックス番号を1からとする
Option Base 1

Sub linearSearch()

    '変数の宣言
    Dim target As Long
    Dim list(5) As Long
    Dim i As Long
    Dim result As String


    '探索する数字を入力
    target = InputBox("対象")
    'データがなかった場合のメッセージをresultに格納
    result = target & "はありませんでした"

    '配列にデータを格納
    For i = 1 To 5
        list(i) = Cells(1, i)
    Next i
    
    '線形探索
    For i = 1 To 5
        If list(i) = target Then
            'データが見つかった場合、resultを上書きし、For文を抜ける
            result = target & "は" & i & "番目にありました"
            Exit For
        End If
    Next i
    
    '結果を表示する
    MsgBox result
    
End Sub