数据结构
网络
关系型数据库管理系统
操作系统
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究Python 中的二分查找（bisect）
在这里，我们将看到 Python 中的 bisect。bisect 用于二分查找。二分查找技术用于查找排序列表中的元素。bisect 是一个库函数。
我们将看到 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
更新于：2020 年 7 月 2 日
1K+ 次查看
广告