bisect 是 Python 提供的一个用于有序列表插入与查找的标准库模块。它可以高效地在已排序的序列中查找插入位置,保持列表的有序性,广泛用于需要维持顺序的插入场景,如搜索建议、实时数据排名等。
常见应用场景:
(1)在有序列表中查找某个值的插入位置。
(2)构建基于有序列表的查找结构(如二分查找)。
(3)插入值并保持列表有序。
(4)实现数值区间映射(如等级分段、价格区间)。
(5)替代线性搜索提高查找效率(O(log n))
◆ ◆ ◆
核心概念
1、bisect 使用二分查找算法,时间复杂度为 O(log n),远优于线性遍历。
2、核心函数包括 bisect_left()、bisect_right()、insort_left() 和 insort_right()。
3、函数名称中的 "left" 和 "right" 决定了重复元素的插入策略:
left:插入到已有相同值的左边。
right:插入到已有相同值的右边。
4、所操作的目标必须是已排序的列表,否则结果不正确。
◆ ◆ ◆
应用举例
例 1: 查找插入位置(左侧插入)
import bisect
scores = [60, 70, 80, 90]
pos = bisect.bisect_left(scores, 80)
print(pos) # 输出:2,插入在第一个 80 的左边例 2:查找插入位置(右侧插入)
import bisect
scores = [60, 70, 80, 80, 90]
pos = bisect.bisect_right(scores, 80)
print(pos) # 输出:4,插入在最后一个 80 的右边例 3:插入值保持列表有序
import bisect
scores = [60, 70, 80, 90]
bisect.insort(scores, 75)
print(scores) # 输出:[60, 70, 75, 80, 90]例 4:使用 insort_left 插入重复值前
import bisect
values = [10, 20, 20, 30]
bisect.insort_left(values, 20)
print(values) # 输出:[10, 20, 20, 20, 30]例 5:实现分段评分(区间查找)
import bisect
thresholds = [60, 70, 80, 90]
grades = ['F', 'D', 'C', 'B', 'A']
score = 85
index = bisect.bisect(thresholds, score)
print(grades[index]) # 输出:B◆ ◆ ◆
常用方法与属性
bisect.bisect_left(a, x, lo=0, hi=len(a))
在 a 中查找 x 的插入位置,偏向左边(重复值左侧)
参数:
a:已排序的列表
x:要插入的值
lo:起始索引(默认 0)
hi:结束索引(默认列表长度)
返回:整数索引,表示插入位置
bisect.bisect_right(a, x, lo=0, hi=len(a))
在 a 中查找 x 的插入位置,偏向右边(重复值右侧)
参数:同上
返回:无(直接修改原列表)
别名:bisect.bisect()
bisect.insort_left(a, x, lo=0, hi=len(a))
将 x 插入列表 a,偏向左边,并保持列表有序
参数:同 bisect_left
返回:无(直接修改原列表)
bisect.insort_right(a, x, lo=0, hi=len(a))
将 x 插入列表 a,偏向右边,并保持列表有序
参数:同 bisect_left
返回:无(直接修改原列表)
别名:bisect.insort()
◆ ◆ ◆
补充说明
1、所有函数都基于列表必须已排序的前提,否则结果可能错误。
2、可通过 key=... 参数自定义排序规则(Python 3.10+ 新增)。
3、若需对复杂对象排序,可考虑结合 sortedcontainers 第三方库使用。
3、bisect 常被用于实现有序集合、有序表、分段函数、查找加速等高性能场景。
“点赞有美意,赞赏是鼓励”
特别声明:以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布,本平台仅提供信息存储服务。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.