探索アルゴリズム ~線形探索~

アルゴリズム


まず前回では、アルゴリズムとはなにか?ということや定番アルゴリズムについてかいつまんで説明した。

ここでは探索アルゴリズムについてまとめていく。
ちなみに探索アルゴリズムには・線形探索・二分探索・ハッシュ探索があるが、ここでは線形探索に触れていく。(二分探索・ハッシュ探索は別の記事に書く)

スポンサーリンク

探索アルゴリズムとは

まず探索アルゴリズムとはなにか。
簡単に言えば、「探索」という名の通り「目的のデータを探し出すアルゴリズム」のことである。

例えばGoogleなどの検索エンジンも探索アルゴリズムを使っている。

では、探索アルゴリズムにはどんな種類があるのかをこれから見ていく。

線形探索法

線形探索法は、簡単に言えば「先頭から順番に並べて探す探索アルゴリズム」である。
そしてこの線形探索法は3つの注意すべきポイントがある。

探索処理は反復構造で記述する

配列に保存されたデータを先頭から順に検索していく

反復構造では終了条件を必ずつけること

線形探索法の考え方

それでは、線形探索法の考え方を先ほど書いた注意すべきポイントに沿って考えてみよう。

例えば、紙が何枚か机の上に並べてあって、その紙をめくると数字が書いてあるとする。
その紙の中から「8」と書いてある紙を探したい、とする。

そのためにはどうするか。
答えは1枚1枚めくっていき、8が出るまで繰り返すのである。
図に書くとこうなる。

これを実際に線形探索法というアルゴリズムを使って探してみよう。
皆さんだったら、どう考えるだろうか。

一般的には、


①カードがあったらめくる
②めくって数を見る
③その数が8かどうかを確認する
④8ではない、ならば次のカードをめくる


の繰り返しになると思う。
これもアルゴリズムとしては間違っていない。

ただ、この方法だとコードが長く複雑になってしまうだろう。
おいてあるカードの枚数が大きければ大きいほど。

なので、ここでは配列を使う。
配列って何?と思った方はこちらで簡単に説明してるので、これを見てほしい。

では、配列を使って線形探索の考え方に沿って書いてみよう。

この場合だと、配列を「arr()」とすると

arr(0) = 9
arr(1)=10
arr(2)=7
arr(3)=8

という配列になる。
これを反復構造で考えると

arr()の()の中に入る数字を変数(例えばi)にして、反復構造を使ってiに1を足しながらループさせ次々に読み込んでいく・・ということになる。
そして8が出たら終了、ということになる。

これを具体的にコードにしてみるとこうなる。

4回目で8が出たら正解
Sub macro1()
    Dim arr As Variant
    
    arr = Application.WorksheetFunction.Transpose(Range("C2:C5"))
    
    Dim msg As String
    Dim i As Integer
    
    For i = 1 To 4
        If arr(i) = 8 Then
            MsgBox i & "回目で8が出ました。終了します"
        End If
    Next i
    
End Sub

これは先程の説明の通り、iに1を足していって8が出たらそこで終了する、というものである。
そして結果は4回目で8が出た、ということである。

このように、配列を使って順番に検索していくアルゴリズムを線形探索法という。

反復構造では必ず終了条件が必要な理由

では、この線形探索で必要なポイントは3つあると書いたが、その重要なポイントの中に「反復構造には必ず終了条件をつけること」と書いてある。
この理由についてあえて述べておきたい。

その理由はずばり、「ループが永遠に終わらなくなるから」である。

特に上記の場合、「必ずどこかのカードのうらに8が書いてあるとは限らない」。
8がどこにもないことだって考えられる。

しかし、終了条件がないと、永遠に8を探し続ける事になってしまいプログラムが終わらない。

ちなみに先程のコードでは、「For~Next」文を使い、更にiが4になった時点で終了するようにしているので、8がなくてもどっちみち終了できるようにしてある。

まとめ

このように、線形探索法は1つ1つデータを見ていきながら結果を判断していく地道なアルゴリズムであることがわかる。
しかしこれだと、データが大きくなっていくに従って処理時間も長くなっていってしまう。

コード自体はシンプルだし、処理の流れも簡単なのは良いが、データが大きくなればなるほど処理時間が長くなっていくのはいただけない。

そこで、次の記事では線形探索法よりももっと効率がいいアルゴリズムを紹介していく。

それでは、また。

タイトルとURLをコピーしました