python~線形探索と二分探索

はじめに

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

線形探索

線形探索とは,例えば

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

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

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

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

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

二分探索

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

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

大西よ,見ているか?