二分探索アルゴリズム

二分探索は、ソートされた要素のリストが入力として与えられるアルゴリズムです.探しているアイテムがリストに含まれている場合、アルゴリズムはその場所に関する情報を返します.それ以外の場合は、null 値を返します.

二分探索では、各試行で残りの数字の半分を排除するために、真ん中の数字を推測します.

def binnary_search(list, item):
    low = 0
    high = len(list) - 1  #1

    while low <= high:
        mid = round(low + high) // 2    #2
        guess = list[mid]

        if guess == item:     #3
            return mid
        if guess > item:      #4
            high = mid - 1
        else:                 #5
            low = mid + 1
    return None

my_list = [1, 2, 3, 5, 7, 9, 11, 23, 123, 345]

print(binnary_search(my_list, 345)) #9
print(binnary_search(my_list, 11)) #6
print(binnary_search(my_list, 15)) #None

このプログラムをいくつかの部分に分解してみましょう:

低と高を使用して、リストのどの部分を検索するかを制御します

検索領域が1つの要素に絞られていない限り、真ん中の要素を選択します

要素が見つかりました

私たちの推測は大きすぎます

私たちの推測は低すぎる

そのような要素はありません

リストの番号は 0 から始まることに注意してください

二分検索は、アイテムのリスト全体を 1 つずつ検索するのに代わる優れた方法です. 10 個の要素のリストを使用した二分探索の速度は O(log 10) であり、最大 4 つの推測が得られます.

Big O 記法についての詳細は、以前の投稿で読むことができます