Python3 bisect_left:返回值与bisect_left文档描述不匹配

Question

我的代码如下：

import bisect
a = [186, 186, 150, 200, 160, 130, 197, 200]
print("left",bisect.bisect_left(a,150))

返回值为：

但是，正如Python3.9的文档中所指定的：

如果x已经出现在a中，则插入点将位于任何现有条目(左侧)之前。

150个存在于列表"a“中，因此返回值应该是1 (i.e., a.index(150) - 1)，但实际返回的值是。请你解释一下原因好吗？

Answer 1

bisect模块以及通常的底层二进制搜索算法是为排序数据而创建的。对于未排序的数据，结果实际上是任意的。

对于排序的bisect_left算法-ness意味着算法不需要检查是否相等:在序列a中，任何现有x的“左边”位置是a[i] < x和x <= a[i + 1]的位置。这是因为排序-ness强制执行a[j] <= a[j+1]。

因此，从技术上讲，插入点将位于(左边)任何现有条目(等于或大于x )之前。排序-保证这是在任何现有的x条目之前。

对于序列[186, 186, 150, 200, 160, 130, 197, 200]和x=150，插入点是0，因为：

• 该列表最初被分为[186, 186, 150, 200]和[160, ...]。
• 右平分的头等于或大于x；假设排序‘，其中不可能有小于x的值。
• 左平分中的所有值都等于或大于x；假设排序‘，插入点必须在所有插入点之前。

左二分法的所有值之前的唯一点是0。