Get first element greater than a given number from a sorted list

Question

I have two lists. List B is like a database to which I need to compare each element of list A, one by one. Lets say

B = [0.6, 1.7, 3, 4.5]
A = [0.6, 0.9, 1.2, 1.5, 2, 2.5, 3, 4, 4.5]

B is a sorted list, so for each A[i] whenever the algorithm finds a number which is >= A[i] in B, it should return that as the output. So my output should look something like:

C = [0.6, 1.7, 1.7, 1.7, 3, 3, 3, 4.5, 4.5]

Could you please suggest me the simplest solution, avoiding nested loops as much as possible?

Your output C makes no sense. 4.5 in B is greater than the first 8 enteries of A so as per your explanation, 4.5 should appear 8 times in C but the C you wrote has 4.5 only twice. This also applies to several other numbers like 3 — Sheldore, Dec 14 '18 at 11:33
What if `B = [0.6, 1.7, 3, 3.9]`? Note that last element in `B` is smaller then last (two) elements in `A`. — iGian, Dec 14 '18 at 13:10

score 5 · Accepted Answer · answered Dec 14 '18 at 11:41

If you can use a 3rd party library, one solution is NumPy via np.searchsorted:

import numpy as np

B = np.array([0.6, 1.7, 3, 4.5])
A = [0.6, 0.9, 1.2, 1.5, 2, 2.5, 3, 4, 4.5]

res = B[np.searchsorted(B, A)]

array([ 0.6,  1.7,  1.7,  1.7,  3. ,  3. ,  3. ,  4.5,  4.5])

This will be more efficient than a sequential loop or an algorithm based on bisect from the standard library.

tobias_k · Answer 2 · 2018-12-14T11:58:53.367

4

Since B is sorted, you can use bisect to binary-search the correct value in B:

>>> B = [0.6, 1.7, 3, 4.5]
>>> A = [0.6, 0.9, 1.2, 1.5, 2, 2.5, 3, 4, 4.5]
>>> import bisect
>>> [B[bisect.bisect_left(B, a)] for a in A]
[0.6, 1.7, 1.7, 1.7, 3, 3, 3, 4.5, 4.5]

This has complexity O(alogb), with a and b being then lengths of A and B respectively. Assuming that A also is sorted, as in your example, you could also do it in O(a+b):

i, C = 0, []
for a in A:
    while B[i] < a:
        i += 1
    C.append(B[i])

Note, however, that both approaches (as well as the other answers posted so far) will fail if A contains a number larger than any number in B.

edited Dec 14 '18 at 11:58

answered Dec 14 '18 at 11:42

tobias_k

81,265
12
120
179

We have thought in the same way. Anyway, +1 – Mihai Alexandru-Ionut Dec 14 '18 at 11:43
1

@MihaiAlexandru-Ionut Oh, I did not see that. Did you just edit that in before I posted my answer? – tobias_k Dec 14 '18 at 11:43
This deserves some credit, it *is* vectorised in one input, at least. +1 – jpp Dec 14 '18 at 11:47

score 3 · Answer 3 · answered Dec 14 '18 at 11:41

3

Just a next would do (if I understood you correctly):

A = [0.6, 0.9, 1.2, 1.5, 2, 2.5, 3, 4, 4.5]
B = [0.6, 1.7, 3, 4.5]

C = [next(b for b in B if b >= a) for a in A]

print(C)  # -> [0.6, 1.7, 1.7, 1.7, 3, 3, 3, 4.5, 4.5]

answered Dec 14 '18 at 11:41

Ma0

15,057
4
35
65

I like this for the list comprehension being being perfectly readable and natural english, even though it may be inefficient for longer lists. – tobias_k Dec 14 '18 at 11:49
2

@tobias_k I think that this question together with the posted answers demonstrates perfectly the power of Python. From very simple, *almost-natural-english* to much more sophisticated and very efficient methods. – Ma0 Dec 14 '18 at 11:53

score 2 · Answer 4 · answered Dec 14 '18 at 11:37

Since your given B list is sorted, you could use:

B = [0.6, 1.7, 3, 4.5]
A = [0.6, 0.9, 1.2, 1.5, 2, 2.5, 3, 4, 4.5]

def first_greater_elem(lst, elem):
    for item in lst:
       if item >= elem:
         return item

Then just use a list comprehension.

C = [first_greater_elem(B,item) for item in A ]

Output

[0.6, 1.7, 1.7, 1.7, 3, 3, 3, 4.5, 4.5]

Another approach could be using bisect_left method from bisect package.

C = [B[bisect_left(B,item)] for item in A ]

Output

[0.6, 1.7, 1.7, 1.7, 3, 3, 3, 4.5, 4.5]

iGian · Answer 5 · 2018-12-14T13:19:47.243

A recursive way (destructive for original lists), works also if list_a contains number larger than list_b:

def pick(lst, ref, res=None):
  if res == None: res = []
  if len(lst) == 0: return res
  if ref[0] >= lst[0]:
    res.append(ref[0])
    lst.pop(0)
  elif len(ref) == 1 and ref[0] < lst[0]:
    # res.extend(lst) # if want to append the rest of lst instead of stop the loop
    # or do whathever is best for you
    return res
  else: ref.pop(0)
  pick(lst, ref, res)
  return res


list_b = [0.6, 1.7, 3, 3.9]
list_bb = [0.5]
list_a = [0.6, 0.9, 1.2, 1.5, 2, 2.5, 3, 4, 4.5]

print(pick(list_a, list_b))
#=> [0.6, 1.7, 1.7, 1.7, 3, 3, 3]

print(pick(list_a, list_bb))
#=> []

Get first element greater than a given number from a sorted list

5 Answers5

Linked