Python

二分探索(python2.7)メモ

More than 1 year has passed since last update.

書籍「なっとく!アルゴリズム」より

備忘録用


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

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