是否有一个库函数,对列表/元组执行二进制搜索,并返回项目的位置,如果找到,如果没有'False' (-1, None等)?

我在bisect模块中找到了bisect_left/right函数,但即使项目不在列表中,它们仍然返回一个位置。这对于它们的预期用途来说是非常好的,但我只是想知道一个项目是否在列表中(不想插入任何东西)。

我想使用bisect_left,然后检查该位置的项是否等于我正在搜索的内容,但这似乎很麻烦(而且我还需要做边界检查,如果数字可以大于我的列表中最大的数字)。如果有更好的方法,我想知道。

为了澄清我需要这个:我知道字典将非常适合这个,但我试图保持尽可能低的内存消耗。我的预期用途是一种双向查找表。我在表中有一个值列表,我需要能够访问基于其索引的值。我还希望能够找到特定值的索引,如果值不在列表中,则为None。

使用字典是最快的方法,但(大约)会增加一倍的内存需求。

我问这个问题时认为我可能忽略了Python库中的一些东西。看来我得自己写代码了,就像Moe建议的那样。


当前回答

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,找到)

其他回答

值得一提的是,bisect文档现在提供了搜索示例: http://docs.python.org/library/bisect.html#searching-sorted-lists

(引发ValueError而不是返回-1或None更加python化——例如,list.index()会这样做。当然,你也可以根据自己的需要调整这些例子。)

这段代码以递归的方式处理整数列表。寻找最简单的情况,即:列表长度小于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)

戴夫·亚伯拉罕斯的解决方案很好。虽然我会把它做得极简:

def binary_search(L, x):
    i = bisect.bisect_left(L, x)
    if i == len(L) or L[i] != x:
        return -1
    return i

我同意@DaveAbrahams使用等分模块的答案是正确的方法。他在回答中没有提到一个重要的细节。

从文档中平分。Bisect_left (a, x, lo=0, hi=len(a))

平分模块不需要预先计算搜索数组。你可以把端点表示为等分线。Bisect_left,而不是使用默认值0和len(a)。

对我的使用更重要的是,寻找一个值X,使给定函数的误差最小化。要做到这一点,我需要一种方法让bisect_left的算法调用我的计算。这真的很简单。

只需要提供一个对象,将__getitem__定义为

例如,我们可以使用平分算法以任意精度找到一个平方根!

import bisect

class sqrt_array(object):
    def __init__(self, digits):
        self.precision = float(10**(digits))
    def __getitem__(self, key):
        return (key/self.precision)**2.0

sa = sqrt_array(4)

# "search" in the range of 0 to 10 with a "precision" of 0.0001
index = bisect.bisect_left(sa, 7, 0, 10*10**4)
print 7**0.5
print index/(10**4.0)

这有点跑题了(因为Moe的回答似乎完整地回答了OP的问题),但从头到尾考虑整个过程的复杂性可能是值得的。如果你把东西存储在一个排序的列表中(这是二进制搜索会有帮助的地方),然后只是检查是否存在,你会遇到(最坏情况,除非指定):

排序的列表

O(n log n)来初始创建列表(如果它是未排序的数据。O(n),如果是排序的) O(log n)次查找(这是二分查找部分) O(n)插入/删除(可能是O(1)或O(log n)平均情况,这取决于您的模式)

而使用set()则会导致

O(n)来创造 O(1)查找 O(1)插入/删除

一个排序列表真正让你得到的是“下一个”,“前一个”和“范围”(包括插入或删除范围),它们是O(1)或O(|范围|),给定一个起始索引。如果你不经常使用这些类型的操作,那么存储为集合,排序显示可能是一个更好的整体交易。Set()在python中只会引起很少的额外开销。