本記事は、ソフトバンクパブリッシングから発行されている「定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)」を参考にPythonでアルゴリズムとデータ構造について学習していきます。
今回は、探索アルゴリズムの中の線形探索法（Linear Search）について学んでいきます。
線形探索法とは
線形探索法（Linear Search）とは、リストに登録されたデータを先頭から順番に調べていくという単純なアルゴリズムです。
もしn個のデータを登録している場合、最小で1回目の探索で目的のデータが見つかり、最大でn回目の探索で目的のデータが見つかるため、平均するとn/2回の探索を実行することになります。
この場合の計算量はO(n)となり、登録されたデータの個数に比例して、探索にかかる時間も増加していきます。
Pythonで線形探索を作ってみる
それでは、Pythonで線形探索法を実装してみます。
# linear_search.py
def linear_search(sequence, target):
index = 0
size = len(sequence)
while index < size:
if sequence[index] == target:
return index
index += 1
return None
seq = [0,2,4,6,8,7,5,9,1]
target = 8
result = linear_search(seq, target)
if result:
print("{} at position: {}.".format(target, result))
else:
print('{} not in sequence.'.format(target))
上記のlinear_search()でリストと対象のデータを渡して検索し、対象のデータが見つかった場合はそのインデックスを返します。
Pythonの場合、for文でenumerate()を使うとリストのインデックスも取得できて便利なのですが、ここでは書籍に倣ってwhile文で書きました。
動作確認
それでは上記で作成したスクリプトを実行してみます。
> python linear_search.py 8 at position: 4.
対象のインデックスを取得することができました。
登録されたデータの個数が少なければ、これで十分な探索が可能となります。
参考書籍
定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)
