Pythonで線形探索（リニアサーチ）を実装する方法を徹底解説

線形探索（Linear Search）は、配列の中から特定の値を探し出すための探索アルゴリズムで、最もシンプルな探索手法として知られています。

この手法の基本的な流れは以下のとおりです。

• 探索したい値を、配列内のすべての要素と先頭から順番に比較していきます。

• 値が見つかった場合は、その要素のインデックスを返します。

• 配列全体を調べても該当する要素が存在しない場合は、-1 または「見つからない」ことを示すメッセージを返します。

疑似コード

linearSearch(int array[], int value):
   for i=0 to len(array):
      if(array[i]==value):
         Element is Present
   //outside for loop
   Element Not Present // element not found in the whole array

実装例

def linearSearch(arr,value):
   for i in range(len(arr)):
      if(arr[i]==value):
         return i
   return -1
array=[1,2,3,4,5,6,7,8,9,10]
value=5
a=linearSearch(array,value)
if(a==-1):
   print("Element not present")
else:
   print("Element present at index",a)

実行結果

Element present at index 4

計算量（時間計算量）

線形探索の最悪計算量は O(n) です。これは、目的の要素が配列の末尾に存在する場合、あるいは配列内にまったく存在しない場合に発生します。

一方、最良計算量は O(1) です。これは、目的の要素が配列の先頭（最初のインデックス）に存在する場合に発生します。

改良版の線形探索

線形探索の最悪計算量は、少しの工夫によって O(n/2) まで改善できます。具体的には、「左」と「右」の2つのポインタを用意し、1回のループで両端から同時に2つの比較を行います。これにより、最悪の場合でも必要な反復回数が半分に抑えられます。

実装例

def linearSearch(arr,value):
   left=0
   right=len(arr)-1
   while(left<=right):
      if(arr[left]==value):
         return left
      elif(arr[right]==value):
         return right
      left+=1
      right-=1
   return -1
array=[1,2,3,4,5,6,7,8,9,10]
value=10
a=linearSearch(array,value)
if(a==-1):
   print("Element not present")
else:
   print("Element present at index",a)

実行結果

Element present at index 9

上記の例では、配列の末尾にあった要素が、最初の反復で見つかっています。最初に紹介した方法では、この要素を見つけるのに10回の反復が必要でした。

また、要素が見つからなかった場合も、2つ目の方法では反復回数が合計 n/2 回で済むため、最悪計算量は O(n/2) となります。

線形探索はどれほど有用か？

線形探索は、二分探索（Binary Search）のように、より優れた時間計算量を持つ探索アルゴリズムが存在するため、実際に使われる場面は限られています。特に、大規模な入力配列に対しては効率が悪いため、実務では用途に応じた適切なアルゴリズムを選択することが重要です。