如何找到一个索引，以便将新项插入已排序列表并保持排序？

Question

a = 132

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

我想知道在有序列表 b 中，a 应该处于第6个位置。

最符合Python风格的方法是什么？

- est

---

在列表b中，a实际上将位于第6个位置而不是第4个。正如@madjar所指出的那样，使用bisect模块中的 bisect.bisect(b, a)可以获取该位置（或bisect_[left|right]），对于插入操作可使用bisect.insort(b, a)或insort[left|right]。 - Christian Witts

Python是否有排序列表？ - Ciro Santilli OurBigBook.com

Answer 1

bisect是Python标准库中的一个模块，非常适合这个任务。该模块中的函数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]。

- Matthias

---

如果a是一个对象或字典，而b是一个已排序的对象或字典列表，会怎样呢？ - Nwawel A Iroume

Answer 2

使用bisect。它的API可能不是最美观的，但这正是您所需要的。

您需要使用bisect.bisect，它会确切地返回您所需的内容。

- madjar

---

为什么它不是“最美的API”？ - Tanmay

Answer 3

对于边缘情况，还存在一些问题。例如，假设您想选择上述 b 中在 (a, c) 范围内的元素，并使用以下方式进行选择：

b[idx_a:idx_c]

那么您需要考虑 a, c 实际上是 b 的元素的情况。请注意：

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

如果a=10，那么两者都将返回索引2。因此，我们需要将索引降低1。幸运的是，有一个函数bisect.bisect_left可以做到这一点，即在我们的示例中。

bisect.bisect_left(b, 10)

提供 1.

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

- nos