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

Question

Python中的二进制搜索(二分法)是否有一个库函数可以对列表/元组执行二进制搜索，如果找到并返回项的位置和‘false’(-1，无，等等)如果不是？我在平分模，但即使项目不在列表中，它们仍然返回一个位置。对于它们的预期用途来说，这是非常好的，但我只想知道列表中是否有项目(不想插入任何内容)。我想用bisect_left然后检查位于该位置的项是否等于我正在搜索的内容，但这似乎很麻烦(我还需要进行边界检查，以检查该数字是否可以大于我列表中最大的数字)。如果有更好的方法，我想知道。编辑为了澄清我需要它做什么：我知道字典将非常适合这一点，但我正试图尽可能地降低内存消耗。我打算用的是一张双向查表。表中有一个值列表，我需要能够根据它们的索引访问这些值。另外，我希望能够找到某个特定值的索引，如果该值不在列表中，则为零。为此使用字典将是最快的方法，但将(大约)增加一倍的内存需求。我在问这个问题时认为，我可能忽略了Python库中的一些内容。看来我得自己写代码了，就像Moe建议的那样。3 回答

Answer 1

from bisect import bisect_leftdef 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

Answer 2

为什么不看一下二分法的代码左/右，并调整它，以适应您的目的。

就像这样：

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