which numbers in list 2 are bigger and smaller than each number in list 1

Question

I am using python. I have two lists, list 1 is 7000 integers long, list 2 is 25000 integers. I want to go through each number in list 1 and find the closest number in list 2 that is bigger and the closest number that is smaller than each number in list 1, and then calculate the difference between these two numbers in list 2. So far I have:

for i in list1:
    for j in list 2:
        if list2[j]<list1[i]:
            a = max(list2)
        elif list2[j]>list1[i]:
            b = min(list2)
            interval = b-a

This doesn't seem to work. I want to find the explicit numbers in list 2 that are less than a specific number in list 1 and know the maximum, and then find out the smallest number in list 2 that is bigger than the number in list 1. Does anyone have any ideas? Thanks

Answer 1

Here's a vectorized solution using NumPy. It should be extremely fast, as it has no loops in Python (apart from the printing stage at the end).

import numpy as np

# set up fake data
l1 = np.array([1.9, 2, 2.1]) # or whatever list you have
l2 = np.array([1, 2, 5, 10]) # as above
l2.sort() # remove this line if it's always sorted

# the actual algorithm
indexes = np.searchsorted(l2, l1, side='right')
lower = l2[indexes - 1]
upper = l2[indexes]
diffs = upper - lower

# print results for debugging
for value, diff in zip(l1, diffs):
    print "value", value, "gap", diff

Here's the output with the hard-coded test data as above:

value 1.9 gap 1
value 2.0 gap 3
value 2.1 gap 3

Answer 2

You can use the bisect module, worst case complexity O(N * logN):

import bisect
lis1 = [4, 20, 26, 27, 30, 53, 57, 76, 89, 101]
lis2 = [17, 21, 40, 49, 53, 53, 53, 53, 70, 80, 81, 95, 99] #this must be sorted
#use lis2.sort() in case lis2 is not sorted
for x in lis1:
       #returns the index where x can be placed in lis2, keeping lis2 sorted
       ind=bisect.bisect(lis2,x) 
       if not (x >= lis2[-1] or x <= lis2[0]):
           sm, bi = lis2[ind-1], lis2[ind]

           if sm == x:  
               """ To handle the case when an item present in lis1 is 
               repeated multiple times in lis2, for eg 53 in this case"""
               ind -= 1
               while lis2[ind] == x:
                   ind -= 1
               sm = lis2[ind]

           print "{} <= {} <= {}".format(sm ,x, bi)

output:

17 <= 20 <= 21
21 <= 26 <= 40
21 <= 27 <= 40
21 <= 30 <= 40
49 <= 53 <= 70
53 <= 57 <= 70
70 <= 76 <= 80
81 <= 89 <= 95

Though this will not output anything for 4 and 101, as 4 is smaller than any element in lis2 and 101 is greater than any element in lis2. But that can be fixed if required.