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つの探索方法の紹介を終わりにします.

大西よ,見ているか?