Python：在一个非常大的数字列表中搜索一个数字列表，允许+或5

Question

情况：

我想做一个匹配：检查一个数字是否在一个数字列表中（非常大的列表，长度超过1e^5，甚至2e^5），允许+或-5错误

示例： 匹配列表[0，15，30，50,60,80,93]->；true中的95 匹配列表[0,15,30,50,60,70,8010523112312312312314，…]->；false

ps：列表不排序（或者我可以排序，如果这样可以提高效率）

我试图使用字典（somekey，和数字列表），但当我在列表中搜索时速度太慢了。在

有更好的主意吗？（我需要搜索3000多个号码）

Answer 1

我喜欢@inspector4dget的答案，但会颠倒过来：

而不是对长列表进行排序和搜索（并将其全部保存在内存中）

对短列表（您要查找的数字）进行排序，然后遍历长列表，查看每个项是否匹配任何搜索项。在

这应该是既快又使用较少的内存。您可能希望使用Python的bisect模块来实现这一点。在

Answer 2

不排序列表（O（n）时间）：

def search(L, x):
    for i in L:
        if -5 <= i-x <= 5:
            return True
    return False

使用排序（O（nlogn）排序时间+O（logn）搜索时间）：

^{pr2}$

Answer 3

如果需要进行多次搜索，只需创建一个集合并在其中进行搜索

>>> L = [0, 15, 30, 50,60,80,93]
>>> S = {i+x for i in L for x in range(-5, 6)}
>>> 95 in S
True

创建set当然是O（n），但是现在查找是O（1）