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

