Pythonによる線形探索の実装をコードを交えて分かりやすく解説する

2023.01.18 2022.08.23

Pythonのシンプルでわかりやすい検索アルゴリズムについて学びましょう。

Linear Search Algorithm（線形探索アルゴリズム

線形探索は、ランダムに与えられた項目のリストから検索するのと非常によく似た動作をします。

例えば、あるページで単語を探す場合、一番上から始めて、探している単語を見つけるまで一つ一つ見ていきます。

これと同じように、線形探索は最初の項目から始めて、項目が見つかるか、リストがなくなるまで、リストの中の各項目をチェックします。

例を挙げてみましょう。

を考える。

そこで、与えられたリストの中から99を見つける必要がある。

最初の項目から始めて、リストの各項目を調べます。

というわけで、5回のチェックの結果、与えられたターゲットが5の位置に見つかりました。

もし、与えられたターゲットがリストになかったら、リスト全体を調べても項目が見つからず、リストの終了後に、その項目は見つからなかったと宣言しているはずです。

なお、我々はリストの各項目を直線的に調べているので、このアルゴリズムにはこのような名前がついています。

Linear Searchはあまり効率の良いアルゴリズムではありません。

リストの各項目に目を通すので、アルゴリズムはリストの項目数に直接影響されます。

言い換えれば、このアルゴリズムの時間計算量はO(n)です。

つまり、リストの項目数がある量倍されると、アルゴリズムを完了するのにかかる時間もその同じ量倍されます。

センチネル、バイナリ、フィボナッチ探索など、より優れた探索アルゴリズムがありますが、線形探索はこれらの中で最も簡単で、最も基本的なものであり、すべてのプログラマーがその使い方を知っておく必要があるということです。

def linear_search(lst, target):

    for i in range(len(lst)):

        if(lst[i] == target):

            return i

    return -1

では、コードを見てみましょう。

引数を2つ取る線形探索の関数を作成します。最初の引数はアイテムを含むリストで、2番目の引数は見つけようとするターゲットアイテムです。
iは与えられたリストのすべてのインデックスを保持し、すなわち、iは 0 からリストの長さ - 1 までとなります。つまり、iは0からリストの長さ-1までです。 * 反復するたびに、ターゲットとインデックスi` にあるリストアイテムを比較します。
もし同じであれば、そのインデックスでターゲットを見つけたことになるので、そのインデックスを返して、関数と同様にループを終了します。
リスト全体をチェックして何も返されなかった場合、コントロールはリストの外に移動し、ターゲットのアイテムがリストにないことを確信するので、アイテムが見つからなかったことを伝える方法として -1 を返します。

では、リスト内の項目とリスト外の項目に対して、このアルゴリズムがどのように動作するかを見てみましょう。

ここで、ターゲットとして2つのアイテムを送信する：99はインデックス4でリストにあり、12はリストにない。

これは、99 がインデックス 4 にあり、12 がリストにないことを示し、したがってアルゴリズムが動作していることを示している。

この記事では、線形探索と呼ばれる非常に簡単でシンプルな探索アルゴリズムについて学びました。

線形探索がどのように機能するか、その効率となぜ “線形 “と名づけられたかについて説明しました。

そして、このアルゴリズムがPythonでどのように書かれ、何をするのかを見て、コードの出力を見てそれを確認しました。

何か学んでいただけたでしょうか。

また別のチュートリアルでお会いしましょう。