Pythonで学ぶアルゴリズム 第9弾：線形探索

#Pythonで学ぶアルゴリズム< 線形探索 >

はじめに

基本的なアルゴリズムをPythonで実装し，アルゴリズムの理解を深める．
その第9弾として線形探索を扱う．

線形探索

探索：多くのデータの中から欲しいデータを見つけること
線形：先頭から順に調べる

つまり，線形探索とは何も複雑なことはせずに順に前から調べて探索すること．

プログラムでの線形探索

リストにデータを格納して，先頭から順に調べる．
これは，プログラムの構造が非常にシンプルで実装も簡単
⇒ データの数が少ない場合には有効な方法

実装

以下に線形探索のコードとそのときの出力を示す．

コード

linear_search.py

"""
2020/12/21
@Yuya Shimizu

線形探索
"""
#線形探索関数
def linear_search(data, target):
    for i in range(len(data)):
        if data[i] == target:
            return i
    return False


if __name__ == '__main__':
    data = [50, 20, 70, 60, 40, 90, 30] #探索を行う対象データ
    target = 40  #探索する値
    found = linear_search(data, target)

    if not found:
        print(f"{target} is not found in the data")
    else:
        print(f"{target} is found at data[{found}]")

出力

40 is found at data[4]

次いで，Falseが返されるときの出力結果も示す．

出力

45 is not found in the data

線形探索関数の簡単な説明

for文で回すが，戻り値としてデータのインデックスを返したいので，あえてfor i in range(len(data))としている．また，for内で，returnすることで，探索の結果見つからないということをfor文の外でreturn Falseと記述するだけで，表現できる．

感想

線形探索は非常に単純で直感と重なる．その他の探索の基礎となるとは思う．これからの学びがまた楽しみとなった．

参考文献

Pythonで始めるアルゴリズム入門　伝統的なアルゴリズムで学ぶ定石と計算量
　　　　　　　　　　　　　　　　　　　　　　　　 増井 敏克　著　　翔泳社