Python标准库 bisect 模块

bisect模块提供了对有序列表进行二分查找和插入的支持。它基于二分算法实现，可以高效地维护有序列表而不必每次插入后都调用排序操作。

主要功能

1. 二分查找函数

• bisect.bisect_left(a, x, lo=0, hi=len(a))

  • 在有序列表a中查找x的插入位置，返回索引使得x插入后能保持有序
  • 如果x已存在，返回最左侧的位置
  • lo和hi参数可以指定查找范围
  • a: 已排序的列表
  • x: 要插入的值
  • lo (可选): 查找范围的起始索引，默认为0
  • hi (可选): 查找范围的结束索引，默认为列表长度
  • 所有位于该索引之前的元素都小于 x
  • 所有位于该索引之后的元素都大于或等于 x
  • 如果 x 已经在列表中，则返回第一个 x 的位置（最左边的位置）

• bisect.bisect_right(a, x, lo=0, hi=len(a)) (或bisect.bisect)

  • 类似bisect_left，但如果x已存在，返回最右侧的位置

2. 插入函数

• bisect.insort_left(a, x, lo=0, hi=len(a))

  • 将x插入到有序列表a中，保持有序
  • 如果x已存在，插入到最左侧

• bisect.insort_right(a, x, lo=0, hi=len(a)) (或bisect.insort)

  • 类似insort_left，但如果x已存在，插入到最右侧

示例用法

import bisect

# 有序列表
data = [1, 3, 5, 7, 9]

# 查找插入位置
index = bisect.bisect_left(data, 4)  # 返回2
print(f"4应该插入到位置{index}")

# 实际插入
bisect.insort_left(data, 4)
print(data)  # 输出 [1, 3, 4, 5, 7, 9]

# 处理重复元素
data = [1, 3, 3, 3, 5]
print(bisect.bisect_left(data, 3))   # 返回1
print(bisect.bisect_right(data, 3))  # 返回4

性能特点

• 时间复杂度：O(log n) 对于查找和插入操作
• 比每次插入后调用sort()更高效（sort()是O(n log n)）
• 适合频繁插入和查找的有序列表场景

实际应用

1. 成绩分级：

def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):
    i = bisect.bisect(breakpoints, score)
    return grades[i]

grades = [grade(score) for score in [33, 65, 77, 89, 95]]
# ['F', 'D', 'C', 'B', 'A']

1. 维护有序列表：

import random

# 生成随机数但保持有序
data = []
for _ in range(10):
    item = random.randint(1, 100)
    bisect.insort(data, item)
print(data)

bisect模块是处理有序序列时的高效工具，特别适合需要频繁插入和查找的场景。