The number of which in list 2 is greater and less than each number in list 1

Question

I am using python. I have two lists, list 1 - 7000 integers, list 2 - 25000 integers. I want to go through each number in list 1 and find the nearest number in list 2, which is larger, and the closest number, which is less than each number in list 1, and then calculate the difference between the two numbers in list 2. So far I have there is:

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

this does not work. I want to find explicit numbers in list 2 that are less than a certain number in list 1 and know the maximum, and then find out the smallest number in list 2 that is greater than the number in list 1. Does anyone have any ideas? thanks

Answer 1

You can use the bisect module, the worst complexity is 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) 

exit:

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

Although this does not output anything for 4 and 101 , since 4 is less than any element in lis2 and 101 is larger than any element in lis2. But this can be fixed if required.

Answer 2

Here is a vector solution using NumPy. It should be very fast, since it has no loops in Python (except for the print phase 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 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 is the output with hard-coded test data as above:

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

Answer 3

First of all, your example is invalid code, or at least it does not do what you want. if you have

 for i in list1: 

then I am not an index, but an element of list1. Therefore, first of all, you would compare I and j, not list [i] and list [j].

It will be easier for us to use the list functions>

 for i in list1: a = max([n for n in list2 if n < i]) b = min([n for n in list2 if n > i]) 

You may need to add if or two to make sure that a and b exist, but it should work as follows.

Answer 4

Here's a solution not using numpy, bisect module or list comprehensions! Enjoy

 list1=[1,2,4,8,16,32,64] list2=[3,6,9,12,15,18,21] correct={4:3, 8:3, 16:3} lower=0 for t in list1: print t difference = 0 index = lower while (difference == 0 and index<len(list2)-1): print "consider %d < %d and %d > %d" % (list2[index],t,list2[index+1],t) if list2[index]<t and list2[index+1] > t: lower = index upper = index + 1 difference = list2[upper] - list2[lower] print "%d difference %d" % (t,list2[upper] - list2[lower]) break index = index +1 if t in correct.keys(): assert(difference == correct[t])