+5 votes
in Programming Languages by (37.5k points)
In a sorted Python list, I want to insert new elements. How can I find indices for the new elements so that the list remains sorted?



If I want to insert 12 into this list, I should get index=1

1 Answer

+2 votes
by (232k points)
selected by
Best answer

The searchsorted() function of the Numpy module returns indices in a list where the new element(s) should be inserted to maintain order.

In the below example, I have generated 10 random integers. I am inserting one new element and a list of new elements into the list. If you try to insert a list of new elements, it returns the indices for all of them.

>>> import numpy as np
>>> import random
>>> a=sorted([random.randint(10,50) for _ in range(10)])
>>> a
[11, 12, 16, 23, 24, 25, 32, 41, 44, 49]
>>> np.searchsorted(a,3)
>>> np.searchsorted(a,13)
>>> np.searchsorted(a,[3,13,20,50])
array([ 0,  2,  3, 10])

If you want to insert an existing element into the list, you can mention the side (right/left) as a parameter to the function.

In the below example, I am inserting 3, and depending on the value of the side, it returned the index of new "3".

>>> a=[1,2,3,4,5]
>>> np.searchsorted(a,3, side="right")
>>> np.searchsorted(a,3, side="left")
>>> np.searchsorted(a,3)