二分探索(python2.7)メモ

書籍「なっとく！アルゴリズム」より
備忘録用

def binary_search(list, item):
    low = 0                               #low とhighを使ってリストの検索部分を追跡
    high = len(list) - 1

    while low <= high:
        mid = (low + high) // 2
        guess = list[mid]          #真ん中の要素を調べる
        if guess == item:        #アイテムを検出
            return mid     #正解ならmid(index)を返す
        if guess > item:    #推測した数字が大きすぎた
            high = mid -1
        else:                   #小さすぎた
            low = mid + 1
    return None    #みつからなければNone

my_list = [1,3,5,7,9]

print binary_search(my_list, 3) #答えは3だけど

2*2*2*2*2*2*2 # log2(100) = 7
log2(100) とは 2を何回掛ければ100になるのかだから
答えは7

対数変換をすると探索回数がだせることがわかった