一尘不染

Python中的二进制搜索(对分)

python

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

我在bisect模块中找到了bisect_left / right函数,但是即使该项目不在列表中,它们仍然会返回位置。这对于他们的预期用途来说是完全可以的,但是我只想知道列表中是否包含某项(不想插入任何内容)。

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

编辑为了弄清楚我需要什么:我知道字典将非常适合此操作,但是我试图将内存消耗保持在尽可能低的水平。我的预期用途将是一种双向查询表。我在表中有一个值列表,我需要能够根据它们的索引访问值。而且我还希望能够找到特定值的索引,或者如果该值不在列表中,则查找None。

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

我问这个问题的原因是我可能忽略了Python库中的某些内容。就像Moe建议的那样,看来我必须编写自己的代码。


阅读 437

收藏
2020-02-20

共1个答案

一尘不染

from bisect import bisect_left

def binary_search(a, x, lo=0, hi=None):  # can't use a to specify default for hi
    hi = hi if hi is not None else len(a)  # hi defaults to 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
2020-02-20