Python:在非常大的数字列表中搜索数字列表，允许+或- 5错误

Question

情况:

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

例子:匹配列表 [0, 15, 30, 50,60,80,93] 中的 95 -> true匹配列表 [0,15,30,50,60,70,80,105,231,123123,12312314,...] 中的 95 -> false

ps:list没有排序(或者我可以排序，这样可以提高效率)

我尝试使用字典(一些键和数字列表)但是当我在列表中进行搜索时它太慢了。

有没有更好的主意？ (我需要搜索 3000+ 个号码)

Answer 1

不对列表进行排序(O(n) 时间):

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

使用排序(O(nlogn) 排序时间 + O(logn) 搜索时间):

def search(L, x):
    L.sort()
    return fuzzyBinSearch(L, x)

def fuzzyBinSearch(L, x):
    mid = len(L)/2
    i = L[mid]
    if if -5 <= i-x <= 5:
        return True
    elif i-x > 5:
        return fuzzyBinSearch(L[mid+1:], x)
    else:
        return fuzzeBinSearch(L[:mid], x)