アルゴリズム コンピューターサイエンス

サーチアルゴリズムとpythonコードを紹介してみる

サーチアルゴリズムとは

サーチアルゴリズムとは、「大量のデータの中から目的のデータを見つけること」です。例えばネット上にあるデータや辞書データ、顧客データなど多くのデータを多く扱うことがよくありますが、データが大量にあるということは、いろいろな情報が知れるのですが、ただそのままの保存では多すぎて、特定の情報を知ることが困難です。そのために大量のデータの中から、目的のデータを探し出すためにサーチを使います。

リニアサーチ

リニアサーチ（線形探索）は最も単純なアルゴリズムです。方法は、先頭から順番に探す値が見つかるまで探していくだけです。 プログラムが単純で実装しやすいですが、配列の中を一つ一つ調べていくので処理速度が遅いです。 pythonコードの例はこのようになります。

a = [3,1,2,4,5]
searchValue = 4
for i in range(len(a)-1):
    for j in range(len(a)):
        if a[i] == searchValue:
            findID = i
            break
print(findID)

結果

3

バイナリサーチ

バイナリサーチ（二分探索）は、高速に検索できるアルゴリズムです。調べる範囲を半分に絞りながら探していく方法なので調べる範囲を素早く絞りこむことが出来ます。範囲を二つに分けて探してくのでバイナリサーチといいます。 しかし、バイナリサーチでは必ずデータをソートしておく（順番に並べる）という処理が必要になります。 pythonコードはこのようになります。

a = [1,2,4,5,10]

searchValue = 4

findID = -1

left = 0
right = len(a) - 1

while left <= right:
    middle = int((left + right) / 2)
    if a[middle] == searchValue:
        findID = middle
        break
    elif a[middle] < searchValue:
        left = middle + 1
    else:
        right = middle - 1
    
    print(findID)

結果

2

参考にした本

アルゴリズムは、アルゴリズムとプログラミング図鑑という本を参考に勉強しました。可愛いイラストで分かりやすく簡潔に書かれておりアルゴリズムが理解できなかった人やプログラミング初級者に非常におすすめです。

楽しく学ぶアルゴリズムとプログラミングの図鑑／森巧尚／まつむらまきお【1000円以上送料無料】 価格:2,689円 (2018/9/19 18:47時点) 感想(0件)