Python bisect模块在有序列表中的二分查找与插入

Python 内置的 bisect 模块提供了一种基于二分查找算法的高效方法，用于在已排序的列表中查找和插入元素。相比于遍历列表的 $O(n)$ 时间复杂度，二分查找的时间复杂度为 $O(\log n)$，这在处理大规模数据时效率提升显著。

1. 模块导入与基础准备

在使用该模块前，确保列表已经是有序的（升序）。如果列表无序，bisect 将无法返回正确结果。

打开 Python 交互式环境或编辑器，输入以下代码导入模块：

import bisect

定义一个已排序的列表作为示例数据：

data = [1, 3, 4, 4, 8, 12]

2. 查找插入位置

核心需求是确定一个新元素应该插入到列表的哪个位置，以保持列表的有序性。bisect 模块主要提供了两个函数：bisect_right 和 bisect_left。

2.1 使用 bisect_right (默认 bisect)

bisect.bisect_right(list, item) 返回的索引是：将该元素插入列表后，该元素会位于所有相同元素的右侧。

执行以下代码，查看返回的索引：

# 目标元素为 4
pos_right = bisect.bisect_right(data, 4)
print(pos_right)  # 输出: 4

在列表 [1, 3, 4, 4, 8, 12] 中，两个 4 的索引分别是 2 和 3。bisect_right 返回 4，意味着新元素将插入到现有的 4 之后。

2.2 使用 bisect_left

bisect.bisect_left(list, item) 返回的索引是：将该元素插入列表后，该元素会位于所有相同元素的左侧。

执行以下代码：

pos_left = bisect.bisect_left(data, 4)
print(pos_left)  # 输出: 2

这意味着新元素将插入到索引 2 的位置，也就是第一个现有的 4 之前，从而成为新的第一个 4。

2.3 两种查找方式的对比

为了更直观地理解二者的区别，参考下表：

3. 执行插入操作

找到了位置后，使用 insort 系列函数直接完成插入，这比手动调用 list.insert() 更方便。

3.1 标准插入 (insort_right)

bisect.insort(list, item) 等同于 bisect.insort_right。它会自动计算位置并插入元素，且时间复杂度优于“先追加后排序”。

运行以下代码：

bisect.insort(data, 4)
print(data)
# 输出: [1, 3, 4, 4, 4, 8, 12]
# 新的 4 被添加到了所有 4 的后面

3.2 左侧插入 (insort_left)

如果希望将相同元素插入到左侧，使用 insort_left：

bisect.insort_left(data, 4)
print(data)
# 输出: [1, 3, 4, 4, 4, 4, 8, 12]
# 新的 4 被添加到了第一个 4 的前面

4. 实际应用场景：成绩等级划分

一个典型的应用场景是根据分数区间查找对应的等级（如 A, B, C）。我们可以维护一个断点列表，利用 bisect 快速定位等级。

定义分数断点（升序）：

# 断点：60分以下为F，60-70为D，70-80为C，80-90为B，90以上为A
# 这里存储断点值
breakpoints = [60, 70, 80, 90]
grades = ['F', 'D', 'C', 'B', 'A']

编写查找函数：

def get_grade(score):
    # bisect_right 返回 score 在 breakpoints 中的位置索引
    # 例如: score=85 -> 在 80 和 90 之间 -> 索引 3 -> grades[3] = 'B'
    index = bisect.bisect_right(breakpoints, score)
    return grades[index]

测试不同分数：

print(get_grade(55))  # 输出: F
print(get_grade(75))  # 输出: C
print(get_grade(92))  # 输出: A
print(get_grade(60))  # 输出: D (bisect_right 确保了 60 分属于 D 而不是 F)

如果使用 bisect_left，对于刚好等于 60 分的情况，它会返回索引 0 (F)，这在很多评分规则中是不准确的。因此这里必须使用 bisect_right。

5. 处理自定义对象（Python 3.10+）

在 Python 3.10 之前，如果需要对包含字典或自定义对象的列表进行操作，通常需要维护一个单独的键列表。Python 3.10 为 bisect 函数添加了 key 参数，简化了这一过程。

定义一个包含字典的列表：

students = [
    {'name': 'Alice', 'score': 85},
    {'name': 'Bob', 'score': 75},
    {'name': 'Charlie', 'score': 95}
]

# 注意：列表必须先按 'score' 排序
# (此处假设已排序，实际操作前请先排序)

使用 key 参数进行查找（假设 Python 3.10+ 环境）：

# 查找分数为 80 的插入位置
# key=lambda x: x['score'] 告诉 bisect 只比较 score 字段
pos = bisect.bisect_right(students, 80, key=lambda s: s['score'])
print(pos)  # 输出: 1 (因为 80 介于 75 和 85 之间)

插入新学生数据并保持有序：

new_student = {'name': 'Dave', 'score': 80}
bisect.insort(students, new_student, key=lambda s: s['score'])

# 此时 Dave (80) 会被插入到 Bob (75) 之后，Alice (85) 之前