探索アルゴリズムとは
探索アルゴリズムは、データの集合の中から特定の要素を見つけるための手法です。
2回に分けて主要な探索アルゴリズムを備忘録的にまとめていきます。
基本的な探索アルゴリズム
ここでは、よく使われる基本的な探索アルゴリズムとして以下の4つを紹介します。
- 線形探索（Linear Search）
- 2分探索法（Binary Search）
- ハッシュ法（hashing）←次回紹介
- 2分探索木（binary tree）←次回紹介
それぞれ、Pythonでの実装方法も紹介していきます。
線形探索（Linear Search）
線形探索（Linear Search）は、データの集合（通常はリストや配列など）を先頭から順番に走査し、目的の要素を探す探索アルゴリズムです。具体的には、最初の要素から順に目的の要素と比較し、一致するかどうかを確認します。もし一致する要素が見つかれば、その位置を返して探索を終了します。しかし、見つからない場合は、全ての要素を比較し終えるまで探索を続けます。
メリット・デメリット
線形探索は非常に単純で実装が容易ですが、データの量が多い場合には効率が低くなる傾向があります。
時間計算量
最悪時間計算量は要素数に比例し、O(n)の時間がかかります。
Pythonでの実装
Data = [17, 19, 1, 3, 36, 7, 25, 100, 5, 55, 12]
len_data = len(Data)
x = 25
# 手動での実装
index = 0
while index < len_data:
if Data[index] == x:
print(f"Found: {index}") # Output: Found: 6
break
else:
index += 1
if index == len_data:
print("Not found")
# in 演算子を使った実装
if x in Data:
index = Data.index(x)
print(f"Found: {index}") # Output: Found: 6
else:
print("Not found")
2分探索法（Binary Search）
2分探索法は、ソートされたデータの集合から目的の要素を効率的に見つけるアルゴリズムです。データを中央で分割し、目的の要素が中央よりも左側にあれば左半分を、右側にあれば右半分を再帰的に探索します。
基本的な仕組み
- データがソートされていることが前提です。まず、データの中央の要素を見ます
- 中央の要素と目的の要素を比較します
- もし中央の要素が目的の要素と一致すれば、探索は成功です
- 一致しない場合は、目的の要素が中央の要素よりも小さいか大きいかによって、探索範囲を半分に絞ります
- 残りの範囲に対して再帰的に探索を行います
メリット・デメリット
2分探索法は、データがソートされている場合に非常に効率的です。しかし、データのソートには時間がかかる場合があります。
時間計算量
最悪時間計算量はO(log n)であり、大規模なデータセットでも迅速に探索が可能です。
Pythonでの実装
Data = [1, 3, 5, 7, 12, 17, 19, 25, 36, 55, 100, 101]
x = 25
# 手動での実装
left = 0
right = len(Data) - 1
mid = (left + right) // 2
while left <= right:
if Data[mid] == x:
print(f"Found: {mid}")
break
elif Data[mid] < x:
left = mid + 1
else:
right = mid - 1
mid = (left + right) // 2
if Data[mid] != x:
print("Not found")
bisect モジュールを使った実装
bisect_left関数は、リストと与えられたデータに対して、2分探索法を用いてデータが挿入可能な位置を返す関数であり、既にデータがリスト内に存在する場合は、挿入位置はリスト内のデータが存在する位置となります。なお、挿入位置が最後になる（挿入するデータが一番大きい）場合について、リストの範囲外にアクセスしないように注意が必要です。
from bisect import bisect_left
index = bisect_left(Data, x)
if index != len(Data) and Data[index] == x:
print(f"Found: {index}")
else:
print("Not found")
まとめと次回予告
今回は、探索アルゴリズムの基本である線形探索と2分探索法について紹介しました。線形探索はデータの先頭から順番に要素を比較し、目的の要素を見つける方法であり、シンプルで実装が容易ですが、大規模なデータセットでは効率が低いという特徴があります。一方、2分探索法はデータがソートされている場合に非常に効率的であり、最悪時間計算量がO(log n)となるため、大規模なデータセットでも素早く探索が可能です。
次回は、探索アルゴリズムの中でも特に効率的な ハッシュ法 と 2分探索木 について詳しく見ていきます。
ハッシュ法はデータをハッシュ関数を用いてハッシュ値に変換し、そのハッシュ値をインデックスとして要素を格納する方法であり、高速な探索が可能です。また、2分探索木は2分探索法を応用したデータ構造であり、データの挿入や削除も効率的に行うことができます。どちらの手法も探索アルゴリズムの中でも重要な役割を果たしていますので、次回もお楽しみに！
それでは、次回もお会いしましょう！