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

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

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

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

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

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


当前回答

如果你只是想看看它是否存在,试着把这个列表变成一个词典:

# Generate a list
l = [n*n for n in range(1000)]

# Convert to dict - doesn't matter what you map values to
d = dict((x, 1) for x in l)

count = 0
for n in range(1000000):
    # Compare with "if n in l"
    if n in d:
        count += 1

在我的机器上,“if n in l”需要37秒,而“if n in d”需要0.4秒。

其他回答

def binary_search_length_of_a_list(single_method_list):
    index = 0
    first = 0
    last = 1

    while True:
        mid = ((first + last) // 2)
        if not single_method_list.get(index):
            break
        index = mid + 1
        first = index
        last = index + 1
    return mid

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

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

使用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

在维基百科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