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

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