极客笔记Python中的二分算法函数
在下面的教程中，我们将使用Python编程语言中的 bisect 模块来学习二分算法。
理解Python的bisect模块
二分算法的目的是找到一个位置，将一个数据元素插入到该位置以保持列表排序。
二分算法使我们能够在插入每个数据元素后保持列表以排序顺序。这是必要的，因为这样可以减少在插入每个数据元素后重复排序列表所需的开销时间。Python在其定义中使用 bisect 模块提供了二分算法。
一些重要的二分函数
现在，让我们看一下在二分算法中起作用的 bisect 模块的一些重要函数:
- bisect(list, num, begin, end)
- bisect_left(list, num, begin, end)
- bisect_right(list, num, begin, end)
- insort(list, num, begin, end)
- insort_left(list, num, begin, end)
- insort_right(list, num, begin, end)
让我们通过一些示例来理解这些函数的工作原理。
理解bisect()函数
bisect() 函数用于返回已排序列表中的位置，在该位置上可以插入传递的数字以保持结果列表的排序顺序。 bisect() 函数接受四个参数 – 需要处理的列表，需要插入的数字，要考虑的列表的起始位置，需要考虑的结束位置。如果数据元素已经存在于列表中，则返回数据元素必须包含的最右位置。
让我们考虑以下示例来演示相同的情况:
示例:
# importing the required library
import bisect
# creating a list
myList = [1, 2, 3, 3, 3, 3, 6, 7, 8, 9]
# printing some statement
print("The rightmost index to insert, so list remains sorted is: ", end = "")
# using the bisect() function
print(bisect.bisect(myList, 3))
输出：
The rightmost index to insert, so list remains sorted is: 6
解释：
在上面的代码片段中，我们导入了所需的库。然后我们创建了一个列表并打印了一些语句。然后我们使用了 bisect() 函数指定列表和要插入和打印值的数字。
理解bisect_left()函数
bisect_left()函数用于返回在排序列表中插入参数中的数字以维持结果列表按排序顺序排列时的位置。bisect_left()接受四个参数 – 需要处理的列表，需要插入的数字，要考虑的列表中的起始点，要考虑的结束点。如果数据元素已经存在于列表中，则返回需要包含数据元素的最左位置。
考虑以下代码段，演示了同样的情况：
示例：
# importing the required library
import bisect
# creating a list
myList = [1, 2, 3, 3, 3, 3, 5, 7, 8, 9]
# printing some statement
print("The leftmost index to insert, so list remains sorted is: ", end = "")
# using the bisect_left() function
print(bisect.bisect_left(myList, 3))
输出：
The leftmost index to insert, so list remains sorted is: 2
解释:
在上面的代码片段中，我们导入了所需的库。然后我们创建了一个列表并打印了一些语句。然后我们使用了 bisect_left() 函数指定列表和要插入和打印的数字。
理解 bisect_right() 函数
bisect_right() 函数与 bisect() 函数类似。如果数据元素已经存在于列表中，则返回包含数据元素的最右边位置。
让我们考虑以下示例来说明相同的问题:
示例:
# importing the required library
import bisect
# creating a list
myList = [1, 2, 3, 3, 3, 3, 5, 7, 8, 9]
# printing some statement
print("The rightmost index to insert, so list remains sorted is: ", end = "")
# using the bisect_right() function
print(bisect.bisect_right(myList, 3))
输出：
The rightmost index to insert, so list remains sorted is: 6
说明：
在上面的代码片段中，我们导入了所需的库。然后我们创建了一个列表并打印了一些语句。然后我们使用了 bisect_right() 函数指定要插入和打印值的列表和数字。
理解insort()函数
insort()函数用于在适当的位置插入数字后返回排序后的列表。 insort()函数接受四个参数 – 需要处理的列表，需要插入的数字，要考虑的列表的起始位置，以及需要考虑的结束位置。如果数据元素已经存在于列表中，则数据元素将插入到最右边的可能位置。
让我们考虑以下示例来演示相同的情况：
示例：
# importing the required library
import bisect
# initializing a list
myList = [1, 2, 3, 3, 3, 3, 5, 7, 8, 9]
# using the insort() function to insert 4 at appropriate position
bisect.insort(myList, 4)
print ("The list after insertion of a new data element using the insort() function is: ")
for i in range(0, 10):
print(myList[i], end = " ")
输出：
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() 函数接受四个参数-需要处理的列表，要插入的数字，要考虑的列表起始位置以及需要考虑的列表结束位置。如果数据元素已经存在于列表中，则数据元素将被插入到最左边的可能位置。
让我们考虑以下示例来演示相同的情况：
示例：
# importing the required library
import bisect
# initializing a list
myList = [1, 2, 3, 3, 3, 3, 5, 7, 8, 9]
# using the insort_left() function to insert 4 at appropriate position
bisect.insort_left(myList, 4)
print ("The list after insertion of a new data element using the insort_left() function is: ")
for i in range(0, 10):
print(myList[i], end = " ")
输出：
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() 函数类似。如果数据元素已经存在于列表中，则将数据元素插入到最右侧的位置。
让我们看一个示例来说明同样的情况:
示例:
# importing the required library
import bisect
# initializing a list
myList = [1, 2, 3, 3, 3, 3, 5, 7, 8, 9]
# using the insort_right() function to insert 4 at appropriate position
bisect.insort_right(myList, 4, 0, 5)
print ("The list after insertion of a new data element using the insort_right() function is: ")
for i in range(0, 10):
print(myList[i], end = " ")
输出：
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 -循环来遍历列表，并为用户打印了元素。