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つの探索方法の紹介を終わりにします.
大西よ,見ているか?
-
前の記事
python~numpyで固有値,固有ベクトル 2020.09.09
-
次の記事
python~tkinterを用いたオセロ(リバーシ)改良版:CPU対戦付き~ 2020.09.23
コメントを書く