Python での線形探索
Harshit Jindal
2023年1月30日
注意
線形検索について詳しく理解したい場合は、線形検索アルゴリズムの記事を参照してください。
線形検索アルゴリズム
ここでは、n 個の要素を含むソートされていない配列 A[] があると仮定して、要素 X を見つけたいとします。
-
左端の要素から始まる配列内のすべての要素を
forループを使って辿り、以下のようにする。A[i]の値がXと一致したら、インデックスiを返します。(Xにマッチする要素が複数存在する場合は、インデックスiを返す代わりに、すべてのインデックスを表示するか、すべてのインデックスを配列に格納してその配列を返します)。- そうでなければ、次の要素に移動します。
- 配列の最後の要素にある場合は、
forループを終了します。
-
一致する要素がなければ
-1を返す。
Python で線形検索の実装
def linearsearch(arr, n, x):
for i in range(0, n):
if arr[i] == x:
return i
return -1
arr = [1, 2, 3, 4, 5]
x = 1
n = len(arr)
position = linearsearch(arr, n, x)
if position == -1:
print("Element not found !!!")
else:
print("Element is present at index", position)
出力：
Element is found at index: 1
上記のアルゴリズムの時間的複雑さは O(n) です。
著者： Harshit Jindal
Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.
LinkedIn