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

スポンサーリンク

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

スポンサーリンク

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

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

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

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

例を挙げてみましょう。

線形探索アルゴリズムの理論的な例

を考える。

  • リスト 19, 2000, 8, 2, 99, 24, 17, 15, 88, 40
  • ターゲット:99

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

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

  • 項目1:19、見つかりませんでした。
  • 項目 2: 2000, 発見されませんでした。
  • 項目3:8、見つかりませんでした。
  • 項目4: 2、見つかりません。
  • 項目5, 99, ターゲットが見つかりました、ループ終了。

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

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

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

効率化に関する注意点

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

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

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

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

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

Pythonで線形探索アルゴリズムを実装する

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 を返します。

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

出力

Linear Search Python Example
Linear Search

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

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

まとめ

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

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

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

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

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

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