AK2Sのプログラム日記

フリーランスプログラマのプログラムに関する日記です

探索アルゴリズム

プログラムのブログをすっごい放置してました(;´Д`) 自分用のメモ程度にこれから徐々に書いていきます。

探索アルゴリズムの種類

大雑把によく使われているもの - 線形探索 - 二分探索

線形探索

検索アルゴリズムの1つ。リストや配列に入ったデータの検索を行う。 先頭から順番に検索を行って、見つかれば終了する。

list = [3, 5, 1, 8, 9, 10, 45, 89, 0, 34, 97, 39, 32]
# sortされていなくても問題ない
item = 32
 
for index in range(0, len(list)):
    if item == list[index]:
        print(f"{index + 1}番目に、{item}を見つけました!")
        break
    elif index == (len(list) - 1):
        print(f"{item}は、listには存在しません")

二分探索

ソート済みのリストや配列に入ったデータ(同一の値はないものとする)に対する検索を行うにあたって、 中央の値を見て、検索したい値との大小関係を用いて、検索したい値が中央の値の右にあるか、左にあるかを判断して、片側には存在しないことを確かめながら検索していく。

大小関係を用いるため、未ソートのリストや大小関係の定義されない要素を含むリストには二分探索を用いることはできない。

if __name__ == '__main__':
    # ソートされてるのが前提条件
    list = [1, 3, 5, 9, 18, 20]
    low = 0
    high = len(list) - 1
    item = 1 #検索したい数値
    
    while low <= high:
        mid = (low + high) // 2 #//で、小数点以下切り捨てることができる
        guess = list[mid]
        if guess == item:
            print(f"見つかりました!{item}")
            break
        elif guess < item:
            low = mid + 1
        elif guess > item:
            high = mid - 1
    if guess != item:
        print(f"{item}は、listに存在しません")