線形探索(リニアサーチ)とは?シンプルで万能な検索アルゴリズム

スポンサーリンク
線形探索(リニアサーチ)とは?シンプルで万能な検索アルゴリズム アルゴリズム

線形探索(リニアサーチ)とは

線形探索とは、

先頭から順に各要素を調べ、目的の要素が見つかるまで(または最後まで)探索を続けるアルゴリズム

です。

 

線形探索は、配列やリストの中から特定の要素を見つけ出すための最もシンプルな方法となります。

 

アルゴリズムの概要

線形探索のアルゴリズム
    • ステップ1
      先頭から順に確認する
    • ステップ2
      現在の要素が探している値と一致するか比較する
      ・一致すれば、その位置を返す
      ・一致しなければ、次の要素に移動
    • ステップ3
      配列の最後まで確認しても見つからなければ、存在しない

配列の中から特定の要素を探す問題を例として考えてみましょう。

与えられた配列:[1, 2, 3, 4, 5, 6, 7, 8, 9]

探す数字:3

線形探索(リニアサーチ)の概要

 

性能

時間計算量

時間計算量は以下の通りです。

時間計算量
  • 平均時間計算量:\(O(N/2)\)
  • 最良の場合: \(O(1)\)
  • 最悪の場合: \(O(N)\)

 

最適化する手段

  • 番兵法(センチネル法)
    配列の末尾に探索対象を追加することで、ループの終了条件チェックを減らすことができます。
  • 並列処理
    データセットを分割して同時に探索します。

線形探索(番兵法)の特徴

 

空間計算量

空間計算量は、 \(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

 

参考文献

コメント

タイトルとURLをコピーしました