python - Python中的二分搜索(二分法)

Question

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

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

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

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

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

我在问这个问题时认为我可能忽略了 Python 库中的某些内容。看来我必须按照 Moe 的建议编写自己的代码。

Answer 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