是否有一个库函数，对列表/元组执行二进制搜索，并返回项目的位置，如果找到，如果没有'False' (-1, None等)?
我在bisect模块中找到了bisect_left/right函数，但即使项目不在列表中，它们仍然返回一个位置。这对于它们的预期用途来说是非常好的，但我只是想知道一个项目是否在列表中(不想插入任何东西)。
我想使用bisect_left，然后检查该位置的项是否等于我正在搜索的内容，但这似乎很麻烦(而且我还需要做边界检查，如果数字可以大于我的列表中最大的数字)。如果有更好的方法，我想知道。
为了澄清我需要这个:我知道字典将非常适合这个，但我试图保持尽可能低的内存消耗。我的预期用途是一种双向查找表。我在表中有一个值列表，我需要能够访问基于其索引的值。我还希望能够找到特定值的索引，如果值不在列表中，则为None。
使用字典是最快的方法，但(大约)会增加一倍的内存需求。
我问这个问题时认为我可能忽略了Python库中的一些东西。看来我得自己写代码了，就像Moe建议的那样。
当前回答
这段代码以递归的方式处理整数列表。寻找最简单的情况，即:列表长度小于2。这意味着答案已经存在，并执行测试以检查正确答案。 如果不正确，则设置中间值并测试其是否正确，如果不正确，则再次调用该函数，但将中间值设置为上限或下限，将其向左或向右移动
def binary_search(intList, intValue, lowValue, highValue):
if(highValue - lowValue) < 2:
return intList[lowValue] == intValue or intList[highValue] == intValue
middleValue = lowValue + ((highValue - lowValue)/2)
if intList[middleValue] == intValue:
return True
if intList[middleValue] > intValue:
return binary_search(intList, intValue, lowValue, middleValue - 1)
return binary_search(intList, intValue, middleValue + 1, highValue)
其他回答
这段代码以递归的方式处理整数列表。寻找最简单的情况，即:列表长度小于2。这意味着答案已经存在，并执行测试以检查正确答案。 如果不正确，则设置中间值并测试其是否正确，如果不正确，则再次调用该函数，但将中间值设置为上限或下限，将其向左或向右移动
def binary_search(intList, intValue, lowValue, highValue):
if(highValue - lowValue) < 2:
return intList[lowValue] == intValue or intList[highValue] == intValue
middleValue = lowValue + ((highValue - lowValue)/2)
if intList[middleValue] == intValue:
return True
if intList[middleValue] > intValue:
return binary_search(intList, intValue, lowValue, middleValue - 1)
return binary_search(intList, intValue, middleValue + 1, highValue)
为什么不看看bisect_left/right的代码并调整它以适合您的目的呢?
是这样的:
def binary_search(a, x, lo=0, hi=None):
if hi is None:
hi = len(a)
while lo < hi:
mid = (lo+hi)//2
midval = a[mid]
if midval < x:
lo = mid+1
elif midval > x:
hi = mid
else:
return mid
return -1
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,找到)
虽然Python中没有显式的二进制搜索算法，但有一个模块- bisect -用于使用二进制搜索在排序列表中找到元素的插入点。这可以被“欺骗”为执行二分搜索。它最大的优势和大多数库代码一样——它是高性能的，经过良好测试的，并且可以正常工作(特别是二进制搜索很难成功实现——特别是在没有仔细考虑边缘情况的情况下)。
基本类型
对于基本类型，如string或int，这是非常简单的-你只需要bisect模块和一个排序列表:
>>> import bisect
>>> names = ['bender', 'fry', 'leela', 'nibbler', 'zoidberg']
>>> bisect.bisect_left(names, 'fry')
1
>>> keyword = 'fry'
>>> x = bisect.bisect_left(names, keyword)
>>> names[x] == keyword
True
>>> keyword = 'arnie'
>>> x = bisect.bisect_left(names, keyword)
>>> names[x] == keyword
False
你也可以用它来查找副本:
...
>>> names = ['bender', 'fry', 'fry', 'fry', 'leela', 'nibbler', 'zoidberg']
>>> keyword = 'fry'
>>> leftIndex = bisect.bisect_left(names, keyword)
>>> rightIndex = bisect.bisect_right(names, keyword)
>>> names[leftIndex:rightIndex]
['fry', 'fry', 'fry']
显然，如果需要，您可以只返回索引，而不是该索引处的值。
对象
对于自定义类型或对象，事情有点棘手:您必须确保实现丰富的比较方法，以便正确地进行比较。
>>> import bisect
>>> class Tag(object): # a simple wrapper around strings
... def __init__(self, tag):
... self.tag = tag
... def __lt__(self, other):
... return self.tag < other.tag
... def __gt__(self, other):
... return self.tag > other.tag
...
>>> tags = [Tag('bender'), Tag('fry'), Tag('leela'), Tag('nibbler'), Tag('zoidbe
rg')]
>>> key = Tag('fry')
>>> leftIndex = bisect.bisect_left(tags, key)
>>> rightIndex = bisect.bisect_right(tags, key)
>>> print([tag.tag for tag in tags[leftIndex:rightIndex]])
['fry']
这应该至少在Python 2.7 -> 3.3中工作
最简单的方法是使用对半分割，然后检查一个位置，看看项目是否在那里:
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
