線形探索(リニアサーチ)とは
線形探索とは、
です。
線形探索は、配列やリストの中から特定の要素を見つけ出すための最もシンプルな方法となります。
アルゴリズムの概要
線形探索のアルゴリズム
-
-
ステップ1先頭から順に確認する
-
ステップ2現在の要素が探している値と一致するか比較する・一致すれば、その位置を返す・一致しなければ、次の要素に移動
-
ステップ3配列の最後まで確認しても見つからなければ、存在しない
-
配列の中から特定の要素を探す問題を例として考えてみましょう。
与えられた配列:[1, 2, 3, 4, 5, 6, 7, 8, 9]
探す数字:3
性能
時間計算量
時間計算量は以下の通りです。
最適化する手段
- 番兵法(センチネル法)
配列の末尾に探索対象を追加することで、ループの終了条件チェックを減らすことができます。 - 並列処理
データセットを分割して同時に探索します。
空間計算量
空間計算量は、 \(O(1)\)です。
特徴
長所
短所
用途
実装(Python)
単純な線形探索の実装
def linear_search(nums, target):
for i in range(len(nums)):
if nums[i] == target:
return i
return -1
nums = [1, 2, 3, 4, 5, 6, 7, 8, 9]
print(linear_search(nums, 3))
print(linear_search(nums, 7))
print(linear_search(nums, 0))
2
6
-1
番兵を使用した実装
def linear_search_use_sentinel(nums, target):
nums.append(target)
i = 0
while nums[i] != target:
i += 1
nums.pop()
if i == len(nums):
return -1
return i
nums = [1, 2, 3, 4, 5, 6, 7, 8, 9]
print(linear_search_use_sentinel(nums, 3))
print(linear_search_use_sentinel(nums, 7))
print(linear_search_use_sentinel(nums, 0))
2
6
-1
コメント