Python中的bisect模块：优雅处理有序序列的艺术

Python 中的 bisect 模块：优雅处理有序序列的艺术

bisect 是 Python 标准库中一个非常优雅且实用的模块，它专门用来在已经排序的序列（通常是列表）中进行二分查找和插入操作。

它的核心价值在于：

• 时间复杂度：O(log n) 的查找和插入定位
• 原地操作：不需要自己写二分查找代码
• 保持有序：插入时自动维持序列的有序性

很多开发者在遇到“有序数组中找位置”“插入不打乱顺序”“查找插入点”等需求时，都会直接使用 bisect，而不是手写二分查找。

一、bisect 模块的核心函数一览

函数	作用	返回值	是否修改原序列	常用场景
bisect.bisect_left(a, x)	找到 x 应该插入的最左位置	索引（int）	否	查找第一个 >= x 的位置
bisect.bisect_right(a, x)	找到 x 应该插入的最右位置	索引（int）	否	查找最后一个 <= x 的位置后一位
bisect.bisect(a, x)	等价于 bisect_right	索引	否	最常用别名
bisect.insort_left(a, x)	将 x 插入到最左合适位置	无（直接修改 a）	是	保持有序插入（偏左）
bisect.insort_right(a, x)	将 x 插入到最右合适位置	无（直接修改 a）	是	保持有序插入（偏右）
bisect.insort(a, x)	等价于 insort_right	无	是	最常用插入函数

一句话记忆：

• bisect_left → 偏左（≤ x 的后面）
• bisect_right → 偏右（≥ x 的前面）
• insort = bisect + insert

二、最常见的使用场景与代码示例

1. 查找插入位置（不插入）

import bisect

scores = [10, 30, 45, 45, 60, 85, 90]

# 想知道 50 分应该插在哪里
pos = bisect.bisect_left(scores, 50)
print(pos)          # 4
print(scores[pos])  # 60   （第一个 >= 50 的位置）

pos = bisect.bisect_right(scores, 45)
print(pos)          # 4
print(scores[pos-1]) # 45   （最后一个 <= 45 的位置）

2. 有序插入（保持列表有序）

import bisect

tasks = [100, 300, 500, 700]

# 插入新任务，按优先级排序
bisect.insort(tasks, 400)
print(tasks)  # [100, 300, 400, 500, 700]

bisect.insort_left(tasks, 300)   # 插入到相同值的左边
print(tasks)  # [100, 300, 300, 400, 500, 700]

3. 统计某个值的出现次数（经典技巧）

def count_occurrences(arr, x):
    # 右边界 - 左边界 = 出现次数
    right = bisect.bisect_right(arr, x)
    left = bisect.bisect_left(arr, x)
    return right - left

arr = [1, 2, 2, 2, 3, 4, 4, 5]
print(count_occurrences(arr, 2))  # 3
print(count_occurrences(arr, 4))  # 2
print(count_occurrences(arr, 7))  # 0

4. 查找最接近的值（上下界结合）

def find_closest(arr, target):
    pos = bisect.bisect_left(arr, target)

    # 如果 pos == 0，只有右边
    if pos == 0:
        return arr[0]

    # 如果 pos == len(arr)，只有左边
    if pos == len(arr):
        return arr[-1]

    # 比较左右两侧谁更接近
    left = arr[pos-1]
    right = arr[pos]

    if target - left <= right - target:
        return left
    else:
        return right

nums = [10, 20, 30, 50, 70, 90]
print(find_closest(nums, 35))  # 30
print(find_closest(nums, 55))  # 50

5. 维护固定长度的有序队列（滑动窗口中常用）

import bisect

class FixedSizeSortedList:
    def __init__(self, capacity):
        self.capacity = capacity
        self.data = []

    def add(self, val):
        bisect.insort(self.data, val)
        if len(self.data) > self.capacity:
            self.data.pop(0)  # 移除最小值（如果是最大堆则 pop(-1)）

    def get_all(self):
        return self.data

q = FixedSizeSortedList(5)
for x in [3, 8, 1, 9, 4, 7, 2, 6]:
    q.add(x)
    print(q.get_all())

三、bisect_left vs bisect_right 的本质区别（最容易混淆）

情况	bisect_left 返回位置	bisect_right 返回位置	典型用途
x 不存在	应该插入的位置	应该插入的位置	查找插入点
x 已存在	第一个 x 的位置	最后一个 x 的后面	左边界 / 右边界
想找第一个 >= x	bisect_left	—	常见下界查询
想找最后一个 <= x	—	bisect_right – 1	常见上界查询

口诀：

• 想插在相同值左边 → bisect_left / insort_left
• 想插在相同值右边 → bisect_right / insort_right
• 统计个数、找边界 → 左右结合使用

四、常见误区与注意事项

1. bisect 要求序列必须已经有序
   如果传入无序列表，结果完全不可预测。
2. bisect 不负责排序
   它只负责在已有序的基础上查找和插入。
3. 对自定义对象排序时需提供 key（Python 3.10+ 支持）

# Python 3.10+
bisect.bisect_left(scores, 80, key=lambda x: x.score)

4. 性能：查找 O(log n)，插入 O(n)（因为 list.insert 是 O(n)）

如果需要大量插入且保持有序，考虑使用 sortedcontainers 第三方库（SortedList）。

五、总结：一句话记住 bisect

bisect 是 Python 提供给有序列表的“二分查找 + 有序插入”瑞士军刀。

• 查找位置 → bisect_left / bisect_right
• 保持有序插入 → insort / insort_left / insort_right
• 统计个数、找边界、滑动窗口极值 → 左右边界组合拳

熟练掌握 bisect，能让很多看起来需要手写二分的代码变得非常优雅和简洁。

有想深入的场景吗？
例如：

• 用 bisect 实现滑动窗口中位数
• bisect 在有序日志查询中的应用
• 与 heapq 结合使用
• sortedcontainers 对比

欢迎继续提问～