【Python入門】線形探索（リニアサーチ）の仕組みと実装方法

本記事では、最も基本的な探索アルゴリズムである「線形探索（リニアサーチ）」の仕組みと、Python 3.xでの実装方法について詳しく解説します。

線形探索とは

線形探索は、配列（リスト）の先頭から順番に要素を一つずつ調べ、目的の値と一致するかどうかを確認していくシンプルな探索手法です。データがソートされていなくても利用できるため、小規模なデータや整列されていないデータを扱う際に手軽で便利です。

アルゴリズムの手順

1. 配列 arr[] の左端（先頭）の要素から順に、目的の値 x と各要素を比較していく
2. x がいずれかの要素と一致した場合、そのインデックス（位置）を返す
3. 配列の最後まで一致する要素が見つからなかった場合、-1 を返す（見つからなかったことを示す）

この一連の流れを図にすると、以下のようになります。

実装例

それでは、実際のPythonコードを見てみましょう。ここでは、文字のリストから特定の文字を探す例を示します。

def linearsearch(arr, x):
    for i in range(len(arr)):
        if arr[i] == x:
            return i
    return -1

arr = ['t','u','t','o','r','i','a','l']
x = 'a'
print("element found at index "+str(linearsearch(arr,x)))

実行結果

element found at index 6

この例では、リストのインデックス6（7番目の要素）に「a」が存在するため、「6」が出力されます。もし目的の値がリスト内に存在しなければ、関数は「-1」を返します。

各変数のスコープは、下図のように表すことができます。

計算量について

線形探索の時間計算量は O(n) です。最悪の場合（目的の要素が配列の末尾にある、または存在しない場合）、すべての要素を調べる必要があります。一方、追加のメモリをほとんど必要としないため、空間計算量は O(1) と非常に効率的です。

まとめ

本記事では、Python 3.xにおける線形探索の仕組みと実装方法を学びました。線形探索はコードがシンプルで理解しやすい反面、データ量が多い場合は処理に時間がかかるという特徴があります。大量のデータやソート済みのデータを扱う場合は、二分探索などのより高速なアルゴリズムを検討するとよいでしょう。