How to find an index at which a new item can be inserted into sorted list and keep it sorted?

python sortedlist
est picture est · Jul 2, 2012 · Viewed 15.8k times · Source 
a = 132

b = [0, 10, 30, 60, 100, 150, 210, 280, 340, 480, 530]

I want to know that a should be in the 6th position in ordered list b.

What's the most pythonic way to do so?

Answer

Matthias picture Matthias · Jul 2, 2012

bisect is a module in the Python Standard Library that is perfect for this task. The function bisect in the module bisect will give you the index of the insertion point for the value.

Let me give a code example for bisect

from bisect import bisect
a = 132
b = [0, 10, 30, 60, 100, 150, 210, 280, 340, 480, 530]
print(bisect(b, a))

The result will be 5 because the list is 0-based, so in fact it is the 6th position.

What you can do know is to use the result for an insert.

index = bisect(b, a)
b.insert(index, a)

or without the intermediate variable

b.insert(bisect(b, a), a)

Now b will be [0, 10, 30, 60, 100, 132, 150, 210, 280, 340, 480, 530].

Related questions

Get random sample from list while maintaining ordering of items?

I have a sorted list, let say: (its not really just numbers, its a list of objects that are sorted with a complicated time consuming algorithm) mylist = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ,9 , 10 ] Is there some python function that will give me N of the items, …

Read More
how does searchsort in python work?

To make my question clear say if I have an array a as Out[123]: [1, 3, 4, 6, 9, 10, 54] When I try to search the numbers in the list, searchsort returns correct value but when I try something not in the list, it returns an …

Read More
How do I list all files of a directory?

How can I list all files of a directory in Python and add them to a list?

Read More