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

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

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

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

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

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


当前回答

Bisect_left找到在给定的排序范围内插入元素的第一个位置p,同时保持排序顺序。如果x在值域内,这就是x的位置。如果p是超过末端的位置,x就找不到。否则,我们可以测试x是否在那里,看看是否找到了x。

from bisect import bisect_left

def binary_search(a, x, lo=0, hi=None):
    if hi is None: hi = len(a)
    pos = bisect_left(a, x, lo, hi)                  # find insertion position
    return pos if pos != hi and a[pos] == x else -1  # don't walk off the end

其他回答

这是手册上的内容:

http://docs.python.org/2/library/bisect.html

8.5.1. 搜索排序列表

上面的bisect()函数在查找插入点时很有用,但在执行普通搜索任务时可能会有些棘手或尴尬。下面5个函数展示了如何将它们转换为排序列表的标准查找:

def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError

因此,稍微修改一下你的代码应该是:

def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    return -1

Bisect_left找到在给定的排序范围内插入元素的第一个位置p,同时保持排序顺序。如果x在值域内,这就是x的位置。如果p是超过末端的位置,x就找不到。否则,我们可以测试x是否在那里,看看是否找到了x。

from bisect import bisect_left

def binary_search(a, x, lo=0, hi=None):
    if hi is None: hi = len(a)
    pos = bisect_left(a, x, lo, hi)                  # find insertion position
    return pos if pos != hi and a[pos] == x else -1  # don't walk off the end

这有点跑题了(因为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中只会引起很少的额外开销。

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

为什么不看看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