二进制搜索计数器

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