線形探索 - Algo-List

線形探索アルゴリズムの解説

線形探索(Linear Search)は、リストや配列などの線形データ構造から特定の値を探す際に使用される基本的なアルゴリズム。この手法は、データ構造の最初から順に要素を1つずつ確認し、目的の値と一致する要素が見つかるまで探索を続ける。

線形探索の動作原理

データ構造の先頭から開始
現在の要素が目的の値と一致するかを判定
一致する場合、その要素のインデックスを返す
一致しない場合、次の要素に進む
データ構造の最後まで到達し、目的の値が見つからなかった場合、特別な値（通常は-1）を返す

Pythonによる実装

# linear_search.py
def linear_search(list, target):
  for i in range(len(list)):
    if list[i] == target:
      return i
    return -1

my_list = [5, 2, 8, 1, 9, 3]
print(linear_search(my_list, 8))# 2
print(linear_search(my_list, 7))# -1

探索の早さ

線形探索は、最悪の場合(目的の値がリストの最後にある、または存在しない場合)、全ての要素を確認する必要があるため、要素数 n に対して O(n) の時間計算量となる。したがって、リストが大きくなるにつれて、探索にかかる時間は線形に増加する。

一方で、リストが既にソート済みの場合、目的の値を発見した時点で探索を終了できるため、平均の時間計算量は O(n/2) となる。

線形探索は単純明快なアルゴリズムだが、データ量が大きくなると非効率になる。そのため、ソートされたデータに対しては二分探索法などの高速なアルゴリズムを使用することが推奨される。しかし、小規模のデータセットや特別な条件下(ソート済みでないデータなど)では、線形探索は簡単に実装でき、適切な選択肢となる。