Help us understand the problem. What is going on with this article?

二分探索(python2.7)メモ

More than 3 years have 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

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

teratera
Python, Django, Webアプリケーション, スクレイピング, Pandas, scikit-learn
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away