关于列表中点的计算:为什么会有
i = (first +last) //2
和last
被初始化为len(a_list) - 1
?从我的快速测试来看,这个算法没有 -1
可以正常工作。
def binary_search(a_list, item):
"""Performs iterative binary search to find the position of an integer in a given, sorted, list.
a_list -- sorted list of integers
item -- integer you are searching for the position of
"""
first = 0
last = len(a_list) - 1
while first <= last:
i = (first + last) / 2
if a_list[i] == item:
return '{item} found at position {i}'.format(item=item, i=i)
elif a_list[i] > item:
last = i - 1
elif a_list[i] < item:
first = i + 1
else:
return '{item} not found in the list'.format(item=item)
最佳答案
最后一个合法索引是 len(a_list) - 1
。该算法将 正常工作,因为first
将始终不超过此值,因此截断均值永远不会超出范围。但是,如果没有 -1,大约一半的时间中点计算将比最佳值大 1,导致速度略有下降。
关于python - 二进制搜索 : weird middle point calculation,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/48572552/