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

问题:

是否有一个库函数在列表/元组上执行二进制搜索,并返回项目的位置(如果找到)和“False”(-1,无等),如果没有?
我在bisect module中找到了bisect_left / right的功能,但是即使该项不在列表中,它们仍然返回一个位置。这是非常好的他们的预期用途,但我只想知道一个项目是否在列表或不(不想插入任何东西)。
我想到使用bisect_left,然后检查该位置的项目是否等于我正在搜索的项目,但这似乎很麻烦(我也需要做边界检查,如果数字可能大于我的最大数量列表)。如果有一个更好的方法,我想知道的。
 编辑要澄清我需要什么:我知道一个字典将非常适合这一点,但我试图保持内存消耗尽可能低。我的预期用途将是一种双向查询表。我在表中有一个值列表,我需要能够根据它们的索引来访问这些值。而且我想要能够找到一个特定值的索引,如果值不在列表中,则返回None。
为此使用字典将是最快的方式,但会(大约)使内存要求翻一番。
我在问这个问题,认为我可能在Python库中忽略了一些东西。如我们所说,似乎我必须编写自己的代码。

回答:

class=”lang-python prettyprint-override”>

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

 
 
Code问答: http://codewenda.com/topics/python/
Stackoverflow: Binary search (bisection) in Python

*转载请注明本文链接以及stackoverflow的英文链接

发表评论

电子邮件地址不会被公开。 必填项已用*标注

14 − 6 =