Python Bisect 模块

在本教程中，我们将学习 bisect 算法，该算法是用 Python 编写的。它的源代码不到 80 行。让我们来介绍一下 bisect 模块。

引言

它基本上是一个二分查找算法，用于查找将给定元素插入已排序列表的插入点。但是，请务必记住，它的函数需要已排序的列表作为参数。列表必须按升序排序。如果传入的列表未按升序排序，则函数不会报错，但结果可能出乎意料。现在让我们来了解它的方法。

重要方法

让我们了解 bisect 模块的一些重要方法。

• bisect_left(a, x, lo=0, hi=None) -

它返回索引 i，在该索引处必须插入值 x，以使列表 a 保持其顺序。如果值 x 已存在于列表中，则索引 i 将位于最左侧的 x 值之前。让我们来看下面的示例。

示例 -

输出

The element to be inserted at place:  2

解释 -

在上面的代码中，我们定义了列表 a，并希望插入 45。我们希望插入 45 以保持 a 的顺序。我们调用了 bisect_left() 方法，该方法返回 2；这就是要插入给定值的位置。

考虑到上面的代码片段，我们尝试通过调用列表对象的 insert() 方法将 x 值插入列表 a 中。

示例 - 2

输出

[23, 40, 45, 61, 82, 100, 12, 14]

解释 -

如上面的代码所示，我们在索引 3 处插入了一个值。让我们看另一个示例，其中我们将使用 Bisect 模块提供的 bisects。

现在，我们将插入列表中已存在的元素。

此外，我们将使用 lo 和 hi 参数。让我们来看下面的示例 -

示例 - 3

输出

The element is to be insorted at: 3
[23, 40, 61, 82, 82, 100, 12, 14]

解释 -

正如我们之前提到的，bisect_left 方法对应于列表中值 x (82) 的第一个匹配项。lo 和 hi 参数用于指定我们要考虑的列表的起始和结束索引。如果我们不传递这些参数，则会考虑整个列表，如前面的示例所示。让我们来看 lo 和 hi 的示例。

示例 - 4

输出

The element is to be inserted at: 3
[23, 40, 61, 82, 82, 100, 12, 14]

解释 -

由于将 lo 和 hi 传递给了 bisect_left() 方法，因此要考虑的列表是 a[2:7]，对应于 [23, 40, 61, 82, 82, 100, 12, 14]。bisect_left 在此切片中查找索引 i，然后根据整个列表返回该索引。

• insort_right(a, x, lo=0, hi=None)

它的工作方式与 insort_left() 相同，只是它使用 bisect_right() 函数来查找需要插入 x 值的位置。让我们来看下面的示例。

示例 -

输出

[10, 20, 30, 40, 40, 40, 70, 60]

如果我们使用 bisect_right 方法，我们将得到相同的结果。

这是使用 Bisect 模块功能的最佳方式。重要的是要指出，bisect_left 和 bisect_right 的时间复杂度为 O(log(n))，因为它们的实现使用了二分查找算法。

但是，insort_left 和 insort_right 的时间复杂度取决于 insert 方法的复杂度。这些方法的时间复杂度为 O(n)。

在上面的示例中，我们使用了整数，但我们也可以使用浮点数或字符串列表。

但是，如果我们使用元组或字符串呢？我们可以使用 bisect_right() 和 bisect_left()。但是，如果我们尝试对字符串或元组使用 insort_left 和 insort_right，我们将收到错误。因为元组和字符串是不可变对象，这些对象没有实现修改列表的 insert 方法。对于不可变对象，它们不像列表那样可以就地修改。

bisect_right 和 insort_right 有别名，因此 bisect_right 可以称为 bisect，而 insort_right 可以称为 insort。

与 bisect 模块相关的问题

让我们用 bisect 模块解决一些有趣的问题。

问题 - 编写 Python 程序，使用二分查找 (bisect) 查找给定数组中三个整数的和为零的组合。

示例 -

输出

[[-40, 0, 40], [-20, -20, 40], [-20, 0, 20]]
[[-6, 1, 5], [-6, 2, 4]]

问题 - 2：编写 Python 程序，使用二分查找 (bisect) 在已排序列表中查找给定数字的第一个出现位置。

解决方案

输出

First occurrence of 3 is present at index 2

问题 - 3：编写 Python 程序，使用二分查找 (bisect) 在已排序列表中查找给定数字的最后一个出现位置。

示例 -

输出

Last occurrence of 3 is present at index 3

结论

在上面的教程中，我们详细讨论了 bisect 模块及其方法。我们看到了一些示例，并了解了 bisect_right 和 bisect_left 方法。该模块用于解决与二分查找相关的问题。