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

Question

情况:

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

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

ps:list没有排序(或者我可以对它进行排序,如果这样可以提高效率)

我试图使用字典(somekey和数字列表)但是当我在列表中进行搜索时它太慢了.

有没有更好的想法？(我需要搜索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)