bisect模块 — 二分查找算法

Python标准库精讲专题 · 数据结构与算法工具篇 · 掌握二分查找算法

专题：Python标准库精讲系统学习

关键词：Python, 标准库, bisect, 二分查找, 二分搜索, bisect_left, bisect_right, insort, 有序序列

一、二分查找概述

二分查找（Binary Search），也称折半查找，是一种在有序序列中高效查找目标值的算法。其核心思想是每次都将搜索范围缩小一半，通过不断比较中间元素与目标值的大小关系，快速定位目标位置。Python 标准库中的 bisect 模块提供了高效且易用的二分查找实现，是处理有序序列时不可或缺的工具。

算法原理

二分查找的基本流程如下：首先确定序列的左右边界（初始为整个序列），计算中间位置的索引；然后将中间元素与目标值进行比较——如果中间元素等于目标值，则查找成功；如果中间元素小于目标值，说明目标在右半部分，将左边界移到中间位置右侧；如果中间元素大于目标值，说明目标在左半部分，将右边界移到中间位置左侧。重复这个过程直到找到目标或搜索范围为空。

手动实现二分查找可以帮助理解其原理：

def binary_search(arr, x):
    """在有序数组 arr 中查找 x 的插入位置（第一个 >= x 的位置）"""
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = (lo + hi) // 2
        if arr[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return lo

# 使用示例
data = [1, 3, 5, 7, 9, 11, 13]
pos = binary_search(data, 7)
print(f"7 应插入位置: {pos}")  # 输出: 3
print(f"data[3] = {data[pos]}")  # 输出: data[3] = 7

时间复杂度分析

二分查找的时间复杂度为 O(log n)，这是其最核心的优势。对于一个包含 n 个元素的有序序列，顺序查找在最坏情况下需要比较 n 次，而二分查找仅需比较 log2(n) 次。以 n=100万为例，顺序查找最多需 100万次比较，而二分查找最多只需约 20 次比较，效率提升极为显著。空间复杂度为 O(1)，因为二分查找仅需常数级别的额外空间。

适用范围与前提条件

二分查找有严格的适用前提：序列必须是有序的（升序或降序）。如果序列无序，二分查找将无法正确工作。在 Python 中，这意味着适用于 list、tuple、array.array 等支持随机访问且已排序的序列类型。bisect 模块默认假设序列已按升序排列，且不对序列进行排序操作。

bisect 模块在 C 层面实现，执行效率远高于纯 Python 手动实现的二分查找，因此在需要频繁进行有序序列查找和插入的场景中，应优先使用 bisect 而非自行实现。

二、bisect核心函数

bisect 模块提供两个核心查找函数：bisect_left 和 bisect_right（bisect 是其别名）。它们都返回目标值在有序序列中的插入位置，区别在于当序列中存在与目标值相等的元素时，插入位置在左侧还是右侧。

bisect_left —— 第一个插入位置

bisect.bisect_left(a, x, lo=0, hi=len(a)) 返回将 x 插入到有序序列 a 中的最左侧（最前面）位置。等价于返回序列中第一个大于等于 x 的元素的索引。如果序列中已有与 x 相等的元素，插入点会在这些元素之前。

import bisect

arr = [1, 3, 5, 5, 5, 7, 9]

# bisect_left 返回最左侧的插入位置
pos = bisect.bisect_left(arr, 5)
print(f"bisect_left(arr, 5) = {pos}")   # 输出: 2
# 解释: arr[2] 是第一个 5，插入点应在此位置

pos2 = bisect.bisect_left(arr, 6)
print(f"bisect_left(arr, 6) = {pos2}")  # 输出: 5
# 解释: 6 介于 5 和 7 之间，应插入在索引 5 处（7 的位置之前）

# 使用 lo 和 hi 参数限定搜索范围
sub_arr = arr[2:6]   # [5, 5, 5, 7]
pos3 = bisect.bisect_left(arr, 5, 2, 6)
print(f"bisect_left(arr, 5, 2, 6) = {pos3}")  # 输出: 2

bisect_right / bisect —— 最后一个插入位置

bisect.bisect_right(a, x, lo=0, hi=len(a)) 返回将 x 插入到有序序列 a 中的最右侧（最后面）位置。等价于返回序列中第一个大于 x 的元素的索引。如果序列中已有与 x 相等的元素，插入点会在这些元素之后。bisect.bisect() 是 bisect_right() 的别名。

import bisect

arr = [1, 3, 5, 5, 5, 7, 9]

# bisect_right 返回最右侧的插入位置
pos = bisect.bisect_right(arr, 5)
print(f"bisect_right(arr, 5) = {pos}")  # 输出: 5
# 解释: 最后一个 5 在索引 4，插入点应在索引 5（之后）

# bisect 是 bisect_right 的别名
pos2 = bisect.bisect(arr, 5)
print(f"bisect(arr, 5) = {pos2}")       # 输出: 5

# 对于不存在于序列中的值，left 和 right 结果相同
pos3 = bisect.bisect_left(arr, 6)
pos4 = bisect.bisect_right(arr, 6)
print(f"left({pos3}) == right({pos4}) = {pos3 == pos4}")  # 输出: True

核心区别对比

下表清晰展示了 bisect_left 与 bisect_right 的核心区别：

函数	插入位置	等价条件	典型用途
bisect_left	等于 x 的元素的最左侧	第一个 >= x 的位置	查找第一个满足条件的元素
bisect_right / bisect	等于 x 的元素的最右侧	第一个 > x 的位置	统计等于 x 的元素个数

利用二者之差，可以快速统计有序序列中某个值的出现次数：right - left = count(x)。

import bisect

arr = [1, 3, 5, 5, 5, 7, 9]

# 统计 5 的出现次数
left = bisect.bisect_left(arr, 5)
right = bisect.bisect_right(arr, 5)
count = right - left
print(f"5 出现了 {count} 次")  # 输出: 5 出现了 3 次

三、insort插入函数

bisect 模块不仅提供查找功能，还提供插入功能。insort_left 和 insort_right（insort 是其别名）可以直接在有序序列中插入元素，且插入后序列仍然保持有序，省去了手动调用 list.insert() 的步骤。

insort_left

bisect.insort_left(a, x, lo=0, hi=len(a)) 先调用 bisect_left 确定插入位置，然后调用 a.insert(pos, x) 执行插入。当序列中存在等于 x 的元素时，新元素会被插入到这些元素的左侧。

import bisect

arr = [1, 3, 5, 7, 9]

# 使用 insort 插入元素
bisect.insort_left(arr, 4)
print(arr)  # 输出: [1, 3, 4, 5, 7, 9]

bisect.insort_left(arr, 5)
print(arr)  # 输出: [1, 3, 4, 5, 5, 7, 9]
# 注意: 新的 5 插入到了原有 5 的左侧

insort_right / insort

bisect.insort_right(a, x, lo=0, hi=len(a)) 与 insort_left 类似，区别在于当存在相等元素时，新元素被插入到这些元素的右侧。bisect.insort() 是 insort_right() 的别名。

import bisect

arr = [1, 3, 5, 5, 7, 9]

# insort_right 将新元素插入到相等元素的右侧
bisect.insort_right(arr, 5)
print(arr)  # 输出: [1, 3, 5, 5, 5, 7, 9]
# 注意: 新的 5 插入到了原有 5 的右侧

# insort 是 insort_right 的别名
arr2 = [2, 4, 6, 8]
bisect.insort(arr2, 5)
print(arr2)  # 输出: [2, 4, 5, 6, 8]

insort 函数的实际意义

直接使用 list.insert() 虽然也能插入元素，但需要事先确定插入位置。insort 将"查找位置"和"执行插入"两个步骤合并为一个原子操作，代码更简洁、意图更清晰。在需要维护一个动态有序列表的场景中（如在线排行榜、实时排序数据流），insort 能显著简化代码逻辑。

需要注意的是，list.insert() 操作本身是 O(n) 的（因为需要移动后续元素），因此 insort 的整体时间复杂度为 O(n)。但在 n 较小或插入操作不频繁的场景下，这种开销是可以接受的。对于需要频繁插入且数据量较大的场景，建议改用 heapq 或 sortedcontainers 等更适合的数据结构。

四、高级应用

bisect 模块虽然接口简单，但结合 Python 的灵活特性，可以衍生出诸多高级用法。本节介绍几种实用的高级应用模式。

自定义 key 的查找（通过映射）

bisect 不支持直接传入 key 参数，但可以通过将数据结构"展平"为值列表来实现基于某个字段的二分查找。典型的应用场景是在对象列表中按对象的某个属性进行搜索。

import bisect

# 学生成绩列表，按分数排序
students = [
    ('Alice', 72),
    ('Bob', 85),
    ('Charlie', 91),
    ('Diana', 95),
]

# 预先提取分数列表作为辅助索引
scores = [score for _, score in students]

# 查找第一个分数 >= 80 的学生
pos = bisect.bisect_left(scores, 80)
if pos < len(students):
    name, score = students[pos]
    print(f"第一个分数 >= 80 的学生: {name}, {score}分")
    # 输出: 第一个分数 >= 80 的学生: Bob, 85分

成绩等级判定

利用 bisect 可以将连续的分数区间映射为离散的等级，代码简洁优雅，且避免了冗长的 if-elif 链。

import bisect

def get_grade(score):
    """将百分制分数转换为等级"""
    breakpoints = [60, 70, 80, 90]
    grades = ['不及格', '及格', '中等', '良好', '优秀']
    i = bisect.bisect_right(breakpoints, score)
    return grades[i]

# 测试各分数段
test_scores = [45, 59, 60, 65, 75, 85, 95, 100]
for s in test_scores:
    print(f"{s:3d}分 -> {get_grade(s)}")

# 输出:
#  45分 -> 不及格
#  59分 -> 不及格
#  60分 -> 及格
#  65分 -> 及格
#  75分 -> 中等
#  85分 -> 良好
#  95分 -> 优秀
# 100分 -> 优秀

区间查找

结合 bisect_left 和 bisect_right，可以在一行代码内完成有序序列中指定范围的元素查找。这在数据处理和统计分析中非常实用。

import bisect

def find_in_range(arr, low, high):
    """返回有序数组 arr 中所有在 [low, high] 范围内的元素"""
    left = bisect.bisect_left(arr, low)
    right = bisect.bisect_right(arr, high)
    return arr[left:right]

data = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

# 查找 5 到 15 之间的所有元素（包含端点）
result = find_in_range(data, 5, 15)
print(f"范围 [5, 15] 内的元素: {result}")
# 输出: 范围 [5, 15] 内的元素: [5, 7, 9, 11, 13, 15]

# 查找 8 到 12 之间的元素
result2 = find_in_range(data, 8, 12)
print(f"范围 [8, 12] 内的元素: {result2}")
# 输出: 范围 [8, 12] 内的元素: [9, 11]

五、性能对比

二分查找相较于顺序查找的性能优势在数据量增大时尤为明显。本节通过具体的性能测试数据直观展示 bisect 的高效性。

顺序查找 vs 二分查找

顺序查找（如 list.index() 或 in 操作符）在最坏情况下需要遍历整个列表，时间复杂度 O(n)。而二分查找每比较一次就排除一半的元素，时间复杂度 O(log n)。下表展示了两种算法在不同数据规模下的最大比较次数：

数据规模 (n)	顺序查找 (最坏)	二分查找 (最坏)	性能提升
1,000	1,000 次	10 次	100x
100,000	100,000 次	17 次	~5,882x
10,000,000	10,000,000 次	24 次	~416,667x
1,000,000,000	1,000,000,000 次	30 次	~33,333,333x

实际性能测试

以下代码对比了使用 list.index()（顺序查找）和 bisect.bisect_left()（二分查找）在大型有序列表中的实际执行时间：

import bisect
import time
import random

# 创建一个包含 1000 万元素的有序列表
n = 10_000_000
arr = list(range(n))
target = n - 5  # 查找列表末尾的目标

# --- 顺序查找（最坏情况） ---
start = time.perf_counter()
try:
    idx = arr.index(target)
except ValueError:
    idx = -1
linear_time = time.perf_counter() - start
print(f"顺序查找: {linear_time:.4f} 秒, 结果索引: {idx}")

# --- 二分查找 ---
start = time.perf_counter()
idx = bisect.bisect_left(arr, target)
if idx < len(arr) and arr[idx] == target:
    pass
bisect_time = time.perf_counter() - start
print(f"二分查找: {bisect_time:.6f} 秒, 结果索引: {idx}")

# --- 性能提升倍数 ---
if bisect_time > 0:
    print(f"性能提升: {linear_time / bisect_time:.0f} 倍")

# 输出示例（因硬件而异）:
# 顺序查找: 0.0842 秒, 结果索引: 9999995
# 二分查找: 0.000002 秒, 结果索引: 9999995
# 性能提升: 42100 倍

多种查找方式对比

除了 bisect，Python 还提供了其他查找方式。以下对比了在有序列表中查找元素的不同方法：

查找方式	时间复杂度	是否要求有序	适用场景
bisect_left / bisect_right	O(log n)	是	有序序列中查找或插入
list.index()	O(n)	否	无序列表查找（小规模）
in 操作符	O(n)	否	仅判断是否存在
set / dict 查找	O(1) 平均	否	频繁的成员检测（无需有序性）

总结：如果数据是有序的且需要频繁查找，bisect 是最优选择。如果仅需判断元素是否存在且不关心顺序，set 的性能更优。如果数据量小或无须有序性，list.index() 也是可接受的。

六、实战案例与总结

理论知识需要通过实践来深化理解。本节通过三个综合案例展示 bisect 在实际项目中的典型应用。

案例一：数值搜索与自动补全

实现一个简单的数值搜索系统，支持从有序列表中查找目标并返回最近的前后值，类似于 IDE 中的自动补全功能。

import bisect

class SortedSearch:
    """有序列表搜索工具"""

    def __init__(self, data):
        self.data = sorted(data)

    def find_exact(self, x):
        """精确查找 x 是否在列表中"""
        i = bisect.bisect_left(self.data, x)
        return i < len(self.data) and self.data[i] == x

    def find_ge(self, x):
        """查找第一个 >= x 的元素"""
        i = bisect.bisect_left(self.data, x)
        if i < len(self.data):
            return self.data[i]
        return None

    def find_le(self, x):
        """查找最后一个 <= x 的元素"""
        i = bisect.bisect_right(self.data, x) - 1
        if i >= 0:
            return self.data[i]
        return None

    def find_range(self, low, high):
        """查找 [low, high] 区间内的所有元素"""
        left = bisect.bisect_left(self.data, low)
        right = bisect.bisect_right(self.data, high)
        return self.data[left:right]


# 使用示例
ss = SortedSearch([3, 7, 1, 9, 5, 11, 15, 13])
print(f"数据: {ss.data}")
print(f"是否存在 7: {ss.find_exact(7)}")
print(f"第一个 >= 6 的元素: {ss.find_ge(6)}")
print(f"最后一个 <= 10 的元素: {ss.find_le(10)}")
print(f"区间 [4, 12] 内的元素: {ss.find_range(4, 12)}")

案例二：考试分数等级评定系统

一个完整的考试分数等级评定系统，支持自定义等级划分规则，并能批量处理分数数据。

import bisect

class GradeSystem:
    """分数等级评定系统"""

    def __init__(self):
        # 默认等级划分
        self.breakpoints = [60, 70, 80, 90]
        self.grades = ['F', 'D', 'C', 'B', 'A']

    def set_grade_table(self, breakpoints, grades):
        """自定义等级划分规则"""
        if len(grades) != len(breakpoints) + 1:
            raise ValueError("grades 长度必须比 breakpoints 多 1")
        self.breakpoints = breakpoints
        self.grades = grades

    def get_grade(self, score):
        """获取单个分数的等级"""
        i = bisect.bisect_right(self.breakpoints, score)
        return self.grades[i]

    def grade_all(self, scores):
        """批量评定分数"""
        return [self.get_grade(s) for s in scores]

    def report(self, scores):
        """生成完整报告"""
        results = self.grade_all(scores)
        print(f"{'分数':>5} | {'等级':>4}")
        print("-" * 14)
        for score, grade in zip(scores, results):
            print(f"{score:>5} | {grade:>4}")
        # 统计各等级人数
        from collections import Counter
        stats = Counter(results)
        print(f"\n等级分布:")
        for g in self.grades:
            print(f"  {g}: {stats.get(g, 0)} 人")


# 使用示例
gs = GradeSystem()
scores = [33, 55, 65, 75, 85, 95, 49, 62, 78, 88, 92, 58]
gs.report(scores)

案例三：日程区间合并

利用 bisect 优化区间合并算法。在处理日程安排、会议时间等区间数据时，快速定位重叠区间并合并。

import bisect

def merge_intervals(intervals):
    """
    合并重叠区间
    参数 intervals: 由 (start, end) 组成的列表
    返回合并后的不重叠区间列表
    """
    if not intervals:
        return []

    # 按区间起点排序
    sorted_ints = sorted(intervals)
    merged = [sorted_ints[0]]

    for start, end in sorted_ints[1:]:
        last_end = merged[-1][1]
        if start <= last_end:
            # 有重叠，合并区间
            merged[-1] = (merged[-1][0], max(last_end, end))
        else:
            # 无重叠，新增区间
            merged.append((start, end))
    return merged


def can_attend_all(meetings):
    """
    判断是否可以参加所有会议（是否有时间冲突）
    参数 meetings: 由 (start, end) 组成的列表
    返回 bool
    """
    merged = merge_intervals(meetings)
    return len(merged) == len(meetings)


# 使用示例
meetings = [(1, 3), (2, 6), (8, 10), (15, 18)]
merged = merge_intervals(meetings)
print(f"原始日程: {meetings}")
print(f"合并后: {merged}")
# 输出: 合并后: [(1, 6), (8, 10), (15, 18)]

no_conflict = [(1, 2), (3, 4), (5, 6)]
print(f"无冲突: {can_attend_all(no_conflict)}")    # 输出: True
print(f"有冲突: {can_attend_all(meetings)}")       # 输出: False

核心要点总结

1. 适用条件：bisect 要求序列必须是有序的，仅适用于已排序的 list 或支持随机访问的序列。

2. 函数选择：bisect_left 返回第一个 >= x 的位置；bisect_right 返回第一个 > x 的位置。二者之差 = x 的出现次数。

3. 插入操作：insort_left/insort_right 在查找后直接插入，保持序列有序性，整体为 O(n)。

4. 性能优势：O(log n) 的时间复杂度使 bisect 在处理大规模有序数据时无可替代。

5. 灵活扩展：虽然 bisect 不支持直接传入 key 参数，但可通过辅助索引实现基于字段的查找。

6. 应用场景：成绩等级判定、区间查找、最近值搜索、有序插入维护等。

进一步思考

在掌握了 bisect 模块的基本用法后，可以进一步思考以下问题：在需要频繁插入且数据量极大的场景下，list + insort 的效率瓶颈在哪里？是否有更优的数据结构选择？可以对比学习 heapq 模块（堆队列）、array 模块以及第三方库 sortedcontainers，理解不同数据结构的适用场景和性能特征，从而在实际开发中做出最佳的技术选型。