Python 中的 Bisect 算法函数

在接下来的教程中，我们将借助 Python 编程语言中的 **bisect** 模块来学习二分算法。

理解 Python bisect 模块

二分算法的目的是在列表中找到一个位置，以便在插入数据元素后能保持列表的有序性。

二分算法能够让我们在插入每个数据元素后都保持列表的有序。这是必要的，因为这样可以减少在每次插入数据元素后重复排序列表所需的开销时间。Python 在其定义中，通过 **bisect** 模块提供了二分算法。

一些重要的二分函数

现在，让我们来看一些 **bisect** 模块的重要函数，它们有助于二分算法的实现。

1. bisect(list, num, begin, end)
2. bisect_left(list, num, begin, end)
3. bisect_right(list, num, begin, end)
4. insort(list, num, begin, end)
5. insort_left(list, num, begin, end)
6. insort_right(list, num, begin, end)

让我们通过一些例子来理解这些函数的工作原理。

理解 bisect() 函数

**bisect()** 函数用于返回排序列表中的位置，在该位置插入参数指定的数字后，可以保持结果列表的有序。**bisect()** 函数接受四个参数：需要处理的列表，需要插入的数字，需要考虑的列表起始位置，需要考虑的列表结束位置。如果数据元素已经存在于列表中，则返回插入该数据元素的右侧位置。

让我们看下面的例子来演示这一点：

示例

输出

The rightmost index to insert, so list remains sorted is: 6

说明

在上面的代码片段中，我们导入了所需的库。然后创建了一个列表并打印了一些语句。接着，我们使用了 **bisect()** 函数，指定了列表和要插入的数字，并打印了该值。

理解 bisect_left() 函数

**bisect_left()** 函数用于返回排序列表中的位置，在该位置插入参数指定的数字后，可以保持结果列表的有序。**bisect_left()** 接受四个参数：需要处理的列表，需要插入的数字，需要考虑的列表起始点，需要考虑的列表结束点。如果数据元素已经存在于列表中，则返回插入该数据元素的左侧位置。

让我们看下面的代码片段来说明这一点：

示例

输出

The leftmost index to insert, so list remains sorted is: 2

说明

在上面的代码片段中，我们导入了所需的库。然后创建了一个列表并打印了一些语句。接着，我们使用了 **bisect_left()** 函数，指定了列表和要插入的数字，并打印了该值。

理解 bisect_right() 函数

**bisect_right()** 函数的工作方式与 **bisect()** 函数类似。如果数据元素已经存在于列表中，则返回插入该数据元素的右侧位置。

让我们看下面的例子来演示这一点：

示例

输出

The rightmost index to insert, so list remains sorted is: 6

说明

在上面的代码片段中，我们导入了所需的库。然后创建了一个列表并打印了一些语句。接着，我们使用了 **bisect_right()** 函数，指定了列表和要插入的数字，并打印了该值。

理解 insort() 函数

**insort()** 函数用于返回在将数字插入到适当位置后排序好的列表。**insort()** 函数接受四个参数：需要处理的列表，需要插入的数字，需要考虑的列表起始位置，以及需要考虑的列表结束位置。如果数据元素已存在于列表中，则数据元素将被插入到最右侧的可能位置。

让我们看下面的例子来演示这一点：

示例

输出

The list after insertion of a new data element using the insort() function is: 
1 2 3 3 3 3 4 5 7 8

说明

在上面的代码片段中，我们导入了所需的库并初始化了列表。然后，我们使用 **insort()** 函数将 4 插入到适当的位置。我们打印了一些语句，使用 **for** 循环遍历列表，并将元素打印给用户。

理解 insort_left() 函数

**insort_left()** 函数用于返回在将数字插入到适当位置后排序好的列表。**insort_left()** 函数接受四个参数：需要处理的列表，需要插入的数字，需要考虑的列表起始位置，以及需要考虑的列表结束位置。如果数据元素已存在于列表中，则数据元素将被插入到最左侧的可能位置。

让我们看下面的例子来演示这一点：

示例

输出

The list after insertion of a new data element using the insort_left() function is: 
1 2 3 3 3 3 4 5 7 8

说明

在上面的代码片段中，我们导入了所需的库并初始化了列表。然后，我们使用 **insort_left()** 函数将 4 插入到适当的位置。我们打印了一些语句，使用 **for** 循环遍历列表，并将元素打印给用户。

理解 insort_right() 函数

**insort_right()** 函数的工作方式与 **insort()** 函数类似。如果数据元素已存在于列表中，则数据元素将被插入到最右侧的可能位置。

让我们看下面的例子来演示这一点：

示例

输出

The list after insertion of a new data element using the insort_right() function is: 
1 2 3 3 3 4 3 5 7 8

说明

在上面的代码片段中，我们导入了所需的库并初始化了列表。然后，我们使用 **insort_right()** 函数将 4 插入到适当的位置。我们打印了一些语句，使用 **for** 循环遍历列表，并将元素打印给用户。