是否有一个库函数，对列表/元组执行二进制搜索，并返回项目的位置，如果找到，如果没有'False' (-1, None等)?
我在bisect模块中找到了bisect_left/right函数，但即使项目不在列表中，它们仍然返回一个位置。这对于它们的预期用途来说是非常好的，但我只是想知道一个项目是否在列表中(不想插入任何东西)。
我想使用bisect_left，然后检查该位置的项是否等于我正在搜索的内容，但这似乎很麻烦(而且我还需要做边界检查，如果数字可以大于我的列表中最大的数字)。如果有更好的方法，我想知道。
为了澄清我需要这个:我知道字典将非常适合这个，但我试图保持尽可能低的内存消耗。我的预期用途是一种双向查找表。我在表中有一个值列表，我需要能够访问基于其索引的值。我还希望能够找到特定值的索引，如果值不在列表中，则为None。
使用字典是最快的方法，但(大约)会增加一倍的内存需求。
我问这个问题时认为我可能忽略了Python库中的一些东西。看来我得自己写代码了，就像Moe建议的那样。
当前回答
在维基百科http://en.wikipedia.org/wiki/Binary_search_algorithm上查看例子
def binary_search(a, key, imin=0, imax=None):
if imax is None:
# if max amount not set, get the total
imax = len(a) - 1
while imin <= imax:
# calculate the midpoint
mid = (imin + imax)//2
midval = a[mid]
# determine which subarray to search
if midval < key:
# change min index to search upper subarray
imin = mid + 1
elif midval > key:
# change max index to search lower subarray
imax = mid - 1
else:
# return index number
return mid
raise ValueError
其他回答
这是基于一个数学断言，即(low + high)/2的下限总是小于high，其中low是下限，high是上限。
def binsearch(t, key, low = 0, high = len(t) - 1):
# bisecting the range
while low < high:
mid = (low + high)//2
if t[mid] < key:
low = mid + 1
else:
high = mid
# at this point 'low' should point at the place
# where the value of 'key' is possibly stored.
return low if t[low] == key else -1
最简单的方法是使用对半分割，然后检查一个位置，看看项目是否在那里:
def binary_search(a,x,lo=0,hi=-1):
i = bisect(a,x,lo,hi)
if i == 0:
return -1
elif a[i-1] == x:
return i-1
else:
return -1
使用dict不会使内存使用量翻倍，除非你存储的对象非常小，因为这些值只是指向实际对象的指针:
>>> a = 'foo'
>>> b = [a]
>>> c = [a]
>>> b[0] is c[0]
True
在这个例子中，'foo'只存储了一次。这对你有影响吗?我们到底要谈多少项呢?
我想使用bisect_left，然后检查是否在那项 position等于我要搜索的内容，但这看起来很麻烦 (我还需要做边界检查，如果数字可以更大 而不是我列表中最大的数字)。如果有更好的方法，我会 我想了解一下。
避免边界检查或相等性检查的一种方法是同时运行bisect_left()和bisect_right():
def find(data, target):
start = bisect_left(data, target)
end = bisect_right(data, target)
return -1 if start == end else start
S是一个列表。 Binary (s, 0, len(s) - 1, find)是初始调用。 函数返回查询项的索引。如果没有这样的项，则返回-1。 def二进制(s, p, q,找到): 如果发现= = s ((p + q) / 2): 返回(p + q) / 2 Elif p==q-1或p==q: 如果发现= = s[问]: 回来问 其他: 返回1 find < s[(p+q)/2]: 返回二进制(s p (p + q) / 2,找到) Elif find > s[(p+q)/2]: 返回二进制(s (p + q) / 2 + 1, q,找到)
