線形探索法 （Pythonによるアルゴリズムとデータ構造）

本記事は、ソフトバンクパブリッシングから発行されている「定本 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)