二進制搜索計數器

Question

我創建的LEN 100

li2 = list(range(100)) 

列表我用下面的二進制搜索功能，用一個計數器，但它需要5個搜索找到50應該找到它的第一次嘗試。 （100/2）= 50個LI2 [50] == 50

def binary_search(li,item): 
    low = 0 
    high = len(li)-1 
    trys = 0 
    while low<=high: 
     mid = int((low + high)/2) 
     guess = li[mid] 
     if guess == item: 
      return'Found',item, 'in', trys,'searches' 
     elif guess > item: 
      trys+=1 
      high = mid - 1 
     else: 
      trys+=1 
      low = mid + 1 
    return item,' not found', trys, ' searches attempted' 

我運行binary_search(li2,50)

並返回下面

('Found', 50, 'in', 5, 'searches') 

Answer 1

range(100)將返回一個列表與從0所有元素，直到99.你的二進制搜索算法將開始對49，而不是搜索上50

Answer 2

爲什麼重新發明輪子的時候可以用bisect，這往往甲肝e本機實現，因此速度非常快。

bisect_left返回列表中的當前項（其必須進行排序當然）的插入位置。如果索引在列表範圍之外，則項目不在列表中。如果指數是中列表範圍和項目位於該指數，那麼你已經找到了：

import bisect 

def binary_search(li,item): 
    insertion_index = bisect.bisect_left(li,item) 
    return insertion_index<len(li) and li[insertion_index]==item 

測試：

li2 = list(range(100)) 
print(binary_search(li2,50)) 
print(binary_search(li2,-2)) 
print(binary_search(li2,104)) 

結果：

True 
False 
False