Python: search a list of numbers in a list of very large numbers, allowing + or - 5 error

Question

Situation:

I want to do a matching: check if a number is in a list of numbers (very large list, length over 1e^5 or even 2e^5) allowing + or - 5 error

Example: match 95 in list [0, 15, 30, 50,60,80,93] -> true match 95 in list [0,15,30,50,60,70,80,105,231,123123,12312314,...] -> false

ps: list are not sorted (or I can sort it if in that way the efficiency can be increased)

I tried to use dictionary (somekey, and list of numbers) but it was too slow when I do the search in the list.

Is there any better ideas? (there are 3000+ of numbers I need to search)

Answer 1

Without sorting your list (O(n) time):

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

With sorting (O(nlogn) time to sort + O(logn) time to search):

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)

Answer 2

If you need to do many searches, you can simply create a set and search in that

>>> 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

Creating the set is O(n) of course, but now lookups are O(1)