Python 库手册：bisect 二分法模块

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 常被用于实现有序集合、有序表、分段函数、查找加速等高性能场景。

“点赞有美意，赞赏是鼓励”