Python中的二进制搜索（二分法）
在这里，我们将看到Python中的等分线。二等分用于二进制搜索。二进制搜索技术用于在排序列表中查找元素。二等分是一个库函数。
我们将在Python中使用bisect看到三个不同的任务。
查找元素的首次出现
bisect.bisect_left（a，x，lo=0，hi=len(a)）此函数用于返回排序列表中x的最左侧插入点。在这种情况下，最后两个参数是可选的。这两个用于在子列表中搜索。
示例
from bisect import bisect_left
def BinSearch(a, x):
i = bisect_left(a, x)
if i != len(a) and a[i] == x:
return i
else:
return -1
a = [2, 3, 4, 4, 5, 8, 12, 36, 36, 36, 85, 89, 96]
x = int(4)
pos = BinSearch(a, x)
if pos == -1:
print(x, "is absent")
else:
print("First occurrence of", x, "is at position", pos)输出结果
First occurrence of 4 is at position 2
寻找小于x的最大值
使用bisect_left选项，我们可以获得更大的值，该值小于x（键）。
示例
from bisect import bisect_left
def BinSearch(a, x):
i = bisect_left(a, x)
if i :
return i-1
else:
return -1
a = [2, 3, 4, 4, 5, 8, 12, 36, 36, 36, 85, 89, 96]
x = int(8)
pos = BinSearch(a, x)
if pos == -1:
print(x, "is absent")
else:
print("Larger value, smaller than", x, "is at position", pos)输出结果
Larger value, smaller than 8 is at position 4
找到最正确的x
bisect.bisect_right（a，x，lo=0，hi=len(a)）此函数用于返回排序列表中x的最右边插入点。在这种情况下，最后两个参数是可选的。这两个用于在子列表中搜索。
示例
from bisect import bisect_right
def BinSearch(a, x):
i = bisect_right(a, x)
if i != len(a) + 1 and a[i-1] == x:
return i-1
else:
return -1
a = [2, 3, 4, 4, 5, 8, 12, 36, 36, 36, 85, 89, 96]
x = int(36)
pos = BinSearch(a, x)
if pos == -1:
print(x, "is absent")
else:
print("Right most occurrence of", x, "is at position", pos)输出结果
Right most occurrence of 36 is at position 9