Python中的二分查找

Question

有没有一个库函数可以在列表或元组中进行二分查找，如果找到就返回这个项的位置，如果没找到就返回'False'（比如-1、None等）呢？

我发现了在bisect模块中的bisect_left和bisect_right函数，但即使找不到项，它们也会返回一个位置。这对于它们的使用场景来说是没问题的，但我只想知道某个项是否在列表中（不想插入任何东西）。

我考虑过使用bisect_left，然后检查那个位置的项是否等于我在找的项，但这样做感觉有点麻烦（而且如果这个数字可能比我列表中最大的数字还大，我还需要做边界检查）。如果有更好的方法，我想知道。

编辑 为了澄清我需要这个的原因：我知道字典非常适合这个，但我想尽量减少内存消耗。我想要的使用方式是一种双向查找表。我在表中有一系列值，需要根据索引来访问这些值。同时，我也想找到某个特定值的索引，如果这个值不在列表中就返回None。

用字典来做这个是最快的方法，但大约会把内存需求翻倍。

我问这个问题是因为我觉得可能在Python库中忽略了什么。看起来我得像Moe建议的那样自己写代码了。

Answer 1

这段内容有点偏题（因为Moe的回答似乎已经完整地回答了提问者的问题），但了解一下整个过程的复杂度可能还是有价值的。如果你在使用一个有序列表来存储东西（这时候二分查找会有帮助），然后只是检查某个元素是否存在，你可能会遇到以下这些情况（最坏情况下，除非另有说明）：

有序列表

• 创建列表的时间复杂度是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中几乎没有额外的开销。

Answer 2

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

Answer 3

bisect_left 是一个用来找到一个元素在已排序范围内可以插入的第一个位置 p 的工具，这样插入后仍然保持这个范围的排序。如果这个元素 x 已经在这个范围内，那么 p 就是 x 的位置。如果 p 是超出范围的最后一个位置，说明没有找到 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