Pythonで線形検索用のプログラムを作成する

線形検索は、配列から特定の値を検索するための検索手法です。これは最も簡単な検索手法です。

この検索手法では、

• 検索する値は、配列内のすべての要素と比較されます。

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

• 特定の要素が配列全体に存在しない場合は、-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つのポインターを使用して、一度に2つの比較を実行することで実行できるため、線形探索の最悪の場合の時間計算量をO（n / 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）です。

線形検索はどの程度役に立ちますか？

より良い時間計算量を提供するバイナリ検索などのより良い検索アルゴリズムがあるため、線形検索が使用されることはめったにありません。線形検索は、大きな入力配列には効率的ではありません。