bisect 库学习文档

一、核心设计思想

bisect 是 Python 标准库内置的二分查找工具集，专门用于已按升序排列的列表，所有函数底层都基于二分查找实现，查找时间复杂度稳定为 O(log n)。

1. 核心前提

所有函数都要求操作的列表已经是升序排列。

如果数组无序，bisect 不会报错，但返回结果完全无意义，这是最常见的踩坑点。

2. 区间约定：左闭右开 [lo, hi)

bisect 所有函数都遵循左闭右开的区间设计：

• 查找范围包含下标 lo 的元素，不包含下标 hi 的元素

• 因此默认右边界 hi = len(a)，刚好覆盖数组全部下标 0 ~ len(a)-1

这种设计的优势：

• 边界统一：空数组时 lo == hi == 0，无需特殊处理

• 天然含义：返回的插入位置，恰好等于「小于目标值的元素个数」

• 减少边界错误：避免了闭区间写法中常见的 off-by-one（差一）问题

3. 函数分类

整个模块共 6 个函数，分为两大类，其中 2 组是别名关系：

分类	函数名	别名	作用
定位查找类	bisect_left	-	查找左侧插入位置（第一个 ≥ x 的下标）
定位查找类	bisect_right	bisect	查找右侧插入位置（第一个 > x 的下标）
有序插入类	insort_left	-	按左侧位置插入元素，保持数组升序
有序插入类	insort_right	insort	按右侧位置插入元素，保持数组升序

二、核心函数源码级详解

bisect 底层由 C 语言实现，性能极高；

官方也提供了逻辑完全一致的纯 Python 参考实现，我们通过源码逐行拆解每个函数的逻辑。

2.1 bisect_left（最核心函数）

函数签名

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

• a：已升序排列的列表

• x：待查找的目标值

• lo：查找左边界（包含），默认 0

• hi：查找右边界（不包含），默认数组长度

纯 Python 源码实现

def bisect_left(a, x, lo=0, hi=None):
    # 左边界合法性校验
    if lo < 0:
        raise ValueError('lo must be non-negative')
    # 右边界默认取数组长度（左闭右开）
    if hi is None:
        hi = len(a)
   
    # 二分核心循环：左闭右开区间 [lo, hi)
    while lo < hi:
        mid = (lo + hi) // 2  # 取中间位置
        if a[mid] < x:
            # 中间值小于目标，目标在右半区，左边界移到 mid+1
            lo = mid + 1
        else:
            # 中间值大于等于目标，目标在左半区，右边界移到 mid
            hi = mid
    # 循环结束时 lo == hi，即为第一个 ≥ x 的下标
    return lo

核心含义

返回值 = 数组中小于 x 的元素个数 = 第一个大于等于 x 的元素的下标 = x 的左侧插入位置。

全边界场景演示

以 a = [2, 4, 4, 4, 6, 8] 为例：

目标值 x	返回结果	含义说明
1	0	比所有元素小，插入到开头
2	0	等于第一个元素，返回其下标
3	1	不存在，返回第一个大于它的位置
4	1	重复元素，返回第一个4 的下标
6	4	匹配到单个元素，返回其下标
8	5	等于最后一个元素，返回其下标
9	6	比所有元素大，返回数组长度

特殊场景：

• 空数组：bisect_left([], 5) → 0

• 单元素数组：bisect_left([5], 5) → 0，bisect_left([5], 6) → 1

2.2 bisect_right（bisect 别名）

函数签名

bisect.bisect_right(a, x, lo=0, hi=len(a))
bisect.bisect(a, x, lo=0, hi=len(a))  # 完全等价的别名

纯 Python 源码实现

def bisect_right(a, x, lo=0, hi=None):
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
   
    while lo < hi:
        mid = (lo + hi) // 2
        # 核心区别：这里是 <=，相等时继续向右找
        if a[mid] <= x:
            lo = mid + 1
        else:
            hi = mid
    return lo

核心含义

返回值 = 数组中小于等于 x 的元素个数 = 第一个大于 x 的元素的下标 = x 的右侧插入位置。

与 bisect_left 的核心差异

只有当 x 在数组中存在重复元素时，两者返回值才不同：

• bisect_left 返回重复元素的最左侧下标

• bisect_right 返回重复元素最右侧下标 + 1

• 两者的差值，恰好等于 x 在数组中出现的次数

如果 x 不在数组中，两个函数返回结果完全相同。

对比演示

同样以 a = [2, 4, 4, 4, 6, 8] 为例：

目标值 x	bisect_left	bisect_right	差值（出现次数）
4	1	4	3
2	0	1	1
5	4	4	0（不存在）
8	5	6	1

2.3 insort_left / insort_right

插入类函数的逻辑非常简单：先调用对应 bisect 函数计算插入位置，再执行列表 insert 操作，保证插入后数组依然升序。

源码逻辑

def insort_left(a, x, lo=0, hi=None):
    idx = bisect_left(a, x, lo, hi)
    a.insert(idx, x)

def insort_right(a, x, lo=0, hi=None):
    idx = bisect_right(a, x, lo, hi)
    a.insert(idx, x)

# 别名
insort = insort_right

关键性能说明

• 二分查找位置：O(log n)

• 列表插入元素：O(n)（动态数组需要移动后续所有元素）

• 整体时间复杂度：O (n)

注意：bisect 只优化了「查找位置」的步骤，并没有加速插入本身。数据量小的时候便捷好用，但如果是十万级以上数据频繁插入，性能会成为瓶颈，此时建议使用专业的有序集合（如第三方库 sortedcontainers.SortedList）。

重复元素插入差异

对于无重复元素的数组，insort_left 和 insort_right 效果完全一致；

只有存在重复元素时，插入的相对位置不同:

a = [2, 4, 6]
bisect.insort_left(a, 4)   # 结果：[2, 4, 4, 6] 新元素插在原有4的左边
bisect.insort_right(a, 4)  # 结果：[2, 4, 4, 6] 新元素插在原有4的右边

三、从基础函数推导所有查找需求

基于 bisect_left 和 bisect_right 两个核心函数，可以推导出有序数组的所有常见边界查找，无需死记硬背，理解原理即可快速推导。

核心公理：

• bisect_left(a, x) → 第一个 ≥ x 的位置 = 小于 x 的元素个数

• bisect_right(a, x) → 第一个 > x 的位置 = 小于等于 x 的元素个数

1. 查找第一个 ≥ x 的元素位置

• 公式：bisect.bisect_left(a, x)

• 边界：返回 len(a) 表示所有元素都小于 x，不存在满足条件的元素

2. 查找第一个 > x 的元素位置

• 公式：bisect.bisect_right(a, x)

• 边界：返回 len(a) 表示所有元素都小于等于 x

3. 查找最后一个 < x 的元素位置

• 公式：bisect.bisect_left(a, x) - 1

• 推导：第一个≥x 的位置左边，所有元素都 < x，减 1 就是最后一个 < x 的元素

• 边界：返回 -1 表示没有小于 x 的元素

4. 查找最后一个 ≤ x 的元素位置

• 公式：bisect.bisect_right(a, x) - 1

• 推导：第一个 > x 的位置左边，所有元素都≤x，减 1 就是最后一个≤x 的元素

• 边界：返回 -1 表示没有满足条件的元素

5. 统计数组中 x 的出现次数

• 公式：bisect.bisect_right(a, x) - bisect.bisect_left(a, x)

• 推导：右边界减左边界，就是所有等于 x 的元素的区间长度

• 结果为 0 表示 x 不存在

6. 判断 x 是否存在于数组中

• 正确写法：

idx = bisect.bisect_left(a, x)
exists = idx < len(a) and a[idx] == x

• 错误写法：a[bisect_left(a,x)] == x（当 x 比所有元素都大时，会报索引越界）

四、进阶用法与技巧

4.1 限定查找 / 插入范围（lo、hi 的实战价值）

lo 和 hi 参数可以让我们只在数组的指定区间内查找 / 插入，无需对数组切片（切片会生成新列表，浪费内存和时间），大数组下性能优势明显。

示例：数组前半段是奇数升序，后半段是偶数升序，只在后半段查找

a = [1, 3, 5, 7, 9, 2, 4, 6, 8, 10]
# 只在下标 [5, 10) 区间（偶数部分）查找4
idx = bisect.bisect_left(a, 4, lo=5)
print(idx)  # 6

4.2 自定义 key 的二分查找

bisect 原生不支持 key 参数（不像 sorted、max），针对对象 / 结构化数据，有三种成熟解决方案：

方案 1：预生成 key 列表（推荐，适合多次查找）

提前提取排序字段组成单独的升序列表，用该列表做二分，再映射回原数据：

students = [("Alice", 85), ("Bob", 90), ("Charlie", 95)]
# 预提取分数列表（和原数组一一对应）
scores = [s[1] for s in students]

idx = bisect.bisect_left(scores, 90)
print(students[idx])  # ("Bob", 90)

方案 2：构造比较元组（适合元组元素）

利用 Python 元组按位置依次比较的特性，构造占位元组直接查找：

students = [("Alice", 85), ("Bob", 90), ("Charlie", 95)]
# 第二个字段是分数，第一个字段用空字符串占位（比任何字符串都小）
idx = bisect.bisect_left(students, ("", 90))
print(students[idx])  # ("Bob", 90)

方案 3：封装带 key 的 bisect（适合复杂对象）

针对自定义类，封装通用的带 key 二分函数：

def bisect_left_key(arr, target, key=lambda x: x):
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = (lo + hi) // 2
        if key(arr[mid]) < target:
            lo = mid + 1
        else:
            hi = mid
    return lo

# 使用示例
class Student:
    def __init__(self, name, score):
        self.name = name
        self.score = score

students = [Student("A", 85), Student("B", 90), Student("C", 95)]
idx = bisect_left_key(students, 90, key=lambda s: s.score)

4.3 降序数组中使用 bisect

bisect 仅支持升序，针对降序数组，最简洁的方式是取负数转为升序问题：

# 降序数组
a = [8, 6, 4, 2]
# 取负数转为升序
neg_a = [-x for x in a]  # [-8, -6, -4, -2]

# 查找第一个 <=4 的位置 → 转为查找第一个 >= -4 的位置
target = 4
idx = bisect.bisect_left(neg_a, -target)
print(idx)  # 2 → 原数组 a[2] = 4，正确

五、性能分析与适用场景

1. 性能对比

操作	时间复杂度	说明
bisect 查找	O(log n)	C 语言实现，比手写 Python 循环快数倍
insort 插入	O(n)	瓶颈在列表插入的元素移动，查找仅占极小开销
线性遍历查找	O(n)	小数组差距不大，大数组差距指数级拉开
先排序再 bisect 查找	O(n log n)	适合一次排序、多次查找的场景

2. 适用场景

• 有序数组的快速边界判断、存在性检查

• 一次排序、多次查询的场景（性价比最高）

• 维护小规模有序数据流

• 算法题经典场景：最长递增子序列、前缀和二分、二分答案

3. 不适用场景

• 频繁插入删除的大数据量有序集合：列表插入是 O (n)，效率低下，建议使用 SortedList

• 完全无序的数组：排序 + 二分的成本可能高于直接遍历

六、常见坑与避坑指南

1. 数组未排序就调用 bisect

后果：不会报错，但返回结果完全错误，极难排查。
避坑：确保数组是升序的；动态维护时只能用 insort 插入，禁止随意 append。

2. 存在性判断遗漏越界检查

错误写法：

if a[bisect.bisect_left(a, x)] == x:  # x比所有元素大时，idx=len(a)，报IndexError

正确写法：先判断下标是否合法，再比较元素。

3. 混淆 left/right 导致逻辑错误

最典型的就是最长递增子序列场景：

• 严格递增 → 用 bisect_left（相等元素替换，不增加长度）

• 非严格递增（允许相等） → 用 bisect_right（相等元素追加，增加长度）

示例验证 nums = [2, 2]：

• bisect_left 结果：长度 1（严格递增，两个 2 不能同时选）

• bisect_right 结果：长度 2（非严格递增，两个 2 可以同时选）

4. 误以为 insort 是 O (log n)

很多人以为「二分插入」就是对数时间，实际上列表是连续内存存储，插入元素必须移动后续所有元素，本质还是 O (n)。

数据量小时没问题，十万级以上频繁插入会有明显性能瓶颈。

七、经典实战案例

案例 1：最长递增子序列（LIS）

import bisect

def length_of_lis(nums, strict=True):
    stack = []
    for n in nums:
        if strict:
            # 严格递增
            idx = bisect.bisect_left(stack, n)
        else:
            # 非严格递增
            idx = bisect.bisect_right(stack, n)
        if idx == len(stack):
            stack.append(n)
        else:
            stack[idx] = n
    return len(stack)

案例 2：前缀和 + 二分查找

经典题目：给定正整数数组和目标值，找出和 ≥ 目标值的最短连续子数组长度。
利用前缀和数组天然升序的特性，用 bisect 快速查找：

import bisect

def min_subarray_len(nums, target):
    n = len(nums)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i+1] = prefix[i] + nums[i]
   
    res = float('inf')
    for i in range(n):
        # 查找第一个 >= prefix[i]+target 的位置
        j = bisect.bisect_left(prefix, prefix[i] + target)
        if j <= n:
            res = min(res, j - i)
    return res if res != float('inf') else 0

案例 3：成绩分档

根据分数快速匹配等级，比 if-elif 链更简洁易维护：

score_thresholds = [60, 75, 90]
grades = ["不及格", "及格", "良好", "优秀"]

def get_grade(score):
    idx = bisect.bisect_right(score_thresholds, score)
    return grades[idx]

print(get_grade(85))  # 良好
print(get_grade(59))  # 不及格