如何找到一个索引，在这个索引中，一个新的项目可以被插入到已排序的列表中并保持其排序？

Question

a = 132

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

我想知道a应该在有序列表b的第6位。

最Python的方法是什么？

Answer 1

使用bisect。它不是最漂亮的API，但正是您所需要的。

您需要使用bisect.bisect，它将返回您想要的内容。

Answer 2

^{}是Python标准库中最适合此任务的模块。模块bisect中的函数bisect将为该值提供插入点的索引。

让我给出一个bisect的代码示例

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

结果将是5，因为列表是基于0的，所以实际上它是第6个位置。

您可以知道的是将结果用于insert。

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

或者没有中间变量

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

现在b将是[0, 10, 30, 60, 100, 132, 150, 210, 280, 340, 480, 530]。

Answer 3

对边缘案件还有进一步的关注。例如，假设您希望选择上述b中(a, c)范围内的元素，并使用

b[idx_a:idx_c]

然后您需要考虑一下a, c实际上是b元素的情况。请注意

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

都会给出索引2。因此，如果a=10，我们需要将索引降低1。幸运的是，有一个函数bisect.bisect_left正是这样做的，即在我们的示例中

bisect.bisect_left(b, 10)

给1。

总的来说，左索引应该使用bisect.bisect_left()和右索引bisect.bisect_right()（与bisect.bisect()相同）来计算。