Python 中的二分查找 (bisect)
pythonserver side programmingprogramming
这里我们将看到 Python 中的二分查找。二分查找用于二分查找。二分查找技术用于在排序列表中查找元素。二分查找是一个库函数。
我们将看到在 Python 中使用二分查找的三个不同任务。
查找元素的第一次出现
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
