python~線形探索と二分探索

はじめに

こんにちは，Keymaleです．今回は線形探索と二分探索です．久々にブログ熱が再燃し頑張って書いてます．最近は備忘録気味なとこもありますが，なるべくわかりやすく書きます．

線形探索

線形探索とは，例えば

a = [1, 2, 3, 4, 5, 6, 7, 8, 9]

という配列があった時に，この中に8という数字があるかどうかを探索するときに，一個目の1から順番に合っているかどうかを調べていく方法になります．以下に実装コードを書きます．

def linear_search(iterable, key):
    for item in iterable:
        if item == key:
            return True
    return False

iterableに探索範囲を，keyに探索する要素を入れてください．探索範囲に要素があればTrue，なければFalseが返ります．例えば

linear_search([1,2,3,4,5,6,7,8,9,10],8)

と書いて実行すれば，Trueが返ってきます．実はpythonでは以下のようにして，線形探索ができます．

8 in [1,2,3,4,5,6,7,8,9,10]

上の例ではリスト内を探索しており，リストとタプルは線形探索し，辞書のキーと集合はハッシュ検索で更に高速で探索されます．

二分探索

二分探索は探索対象がソートされている場合にのみ使えます．探索対象の真ん中と探索する要素を比較して，要素のほうが大きければ半分より大きい方を，小さければ，半分より小さい方を探索します．そしてまた半分にした探索対象の真ん中を比較して，，，ということを繰り返して探索します．コードは以下のようになります．

def binary_search(sequence, key):
    low = 0
    high = len(sequence) - 1
    while low <= high:
        mid = (low + high) //2
        if sequence[mid] < key:
            low = mid + 1
        elif sequence[mid] > key:
            high = mid - 1
        else : 
            return True
    return False

sequenceに探索範囲を，keyに探索する要素を入れ，要素が含まれていればTrue，そうでなければFalseが返ります．以上で2つの探索方法の紹介を終わりにします．

大西よ，見ているか？