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

Question

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 1

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

Answer 2

Use bisect. It's not the most beautiful API, but it's exactly what you need.

You'll want to use bisect.bisect, which returns exactly what you want.

Answer 3

There is further concern with edge cases. For example, suppose you want to select the elements in the aforementioned b in the range of (a, c) and you pick them out using

b[idx_a:idx_c]

then you need to think about the case where a, c are actually elements of b. Note that

bisect.bisect(b, 10)
bisect.bisect(b, 11)

would both give index 2. Thus if a=10 we need to lower the index by 1. Fortunately, there is a function bisect.bisect_left which does exactly this, i.e., in our example

bisect.bisect_left(b, 10)

gives 1.

Overall, the left index should be computed using bisect.bisect_left() and the right index bisect.bisect_right() (which is the same as bisect.bisect()).