Pythonで学ぶ線形探索（リニアサーチ）の基本と実装方法

この記事では、最も基本的な検索アルゴリズムの一つである「線形探索（Linear Search）」の仕組みを理解し、Python 3.xでの実装方法をわかりやすく解説します。

線形探索のアルゴリズム

• 配列 arr[] の左端の要素から順に、目的の要素 x と各要素を一つずつ比較していきます
• x がいずれかの要素と一致した場合、そのインデックス（位置）を返します
• x が配列内のどの要素とも一致しなかった場合、-1 を返すか「要素が見つからない」ことを示します

それでは、このアプローチの流れを視覚的に確認してみましょう。

実装例

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)))

このコードでは、forループを使ってリストの要素を先頭から順番に（線形に）走査しています。変数 x の値「a」はインデックス6の位置に存在するため、7回目の比較で一致し、そのインデックスが返されます。

実行結果

element found at index 6

計算量のポイント

線形探索の時間計算量は O(n) です。最悪の場合、配列内のすべての要素を確認する必要があるためです。一方、目的の要素が先頭にあれば1回の比較で見つかるため、最良ケースは O(1) となります。データ量が少ない場合や、ソートされていないデータを扱う際には、シンプルで有効な手法といえます。

まとめ

この記事では、Pythonにおける線形探索の仕組みと実装方法について学びました。線形探索はロジックが直感的で実装も簡単なため、検索アルゴリズムを学ぶ最初のステップとして最適です。ただし、大規模なデータセットを扱う場合は、二分探索などより効率的なアルゴリズムの活用も検討するとよいでしょう。