前言

二分查找（binary search）是算法的入门课，但 Python 标准库已经把它封装好了——bisect模块。它提供在已排序（升序）序列上做二分定位和插入的函数。很多人第一次用会踩同一个坑：以为bisect返回的是「找到了没有」或者「元素的下标」。都不是。它返回的是一个「插入点」——如果要保持有序，新元素应该插在这里。

官方文档说得很直接：这个模块的函数「设计用来定位插入点」，因此它们从不调用__eq__来判断是否找到，只用<比较，返回一个位于两个值之间的插入位置。理解这一点，bisect的绝大多数困惑就解开了。

本文专讲bisect：bisect_left和bisect_right（bisect是后者的别名）的区别、insort的插入、在有序序列上的查找，以及「怎么用插入点反推出标准的查找结果」。示例以 Python 3.8 为基准，key参数需要Python 3.10+，会单独标注。

一、两个核心函数：bisect_left与bisect_right

签名分别是bisect_left(a, x, lo=0, hi=len(a), *, key=None)和bisect_right(a, x, lo=0, hi=len(a), *, key=None)。bisect是bisect_right的别名，两者完全等价。

差别在遇到相等的已有元素时，插入点在左边还是右边：

• 
  
• bisect_left：插在已有相等元素之前（左）。
• 
  
• bisect_right：插在已有相等元素之后（右）。
• 
  

# 适用于 Python 3.8+
import bisect

a = [10, 20, 20, 20, 30]
print(bisect.bisect_left(a, 20)) # 1，第一个 20 之前
print(bisect.bisect_right(a, 20)) # 4，最后一个 20 之后
print(bisect.bisect(a, 20)) # 4，bisect 就是 bisect_right

对不存在的元素，两者返回同一个值：

# 适用于 Python 3.8+
print(bisect.bisect_left(a, 25)) # 4
print(bisect.bisect_right(a, 25)) # 4

官方文档给出的不变式可以帮助记忆：bisect_left返回的ip把数组切成两段，左段满足所有元素< x，右段满足所有元素>= x；bisect_right则是左段<= x、右段> x。

二、返回值的意义：插入点，不是命中

这是全篇最该记住的一点。看下面这个容易误用的例子：

# 适用于 Python 3.8+
import bisect

a = [10, 20, 30]
i = bisect.bisect_left(a, 20)
print(i) # 1
print(a[i] == 20) # True —— 这次碰巧找到了

j = bisect.bisect_left(a, 25)
print(j) # 2
print(a[j] == 25) # False —— 25 根本不在表里

bisect_left对 25 也返回了一个合法位置（2），但 25 并不存在。所以「返回值」本身不能作为「找到/没找到」的判断依据，它只是「如果插入，插哪里」。

要把它变成真正的等值查找，必须拿到位置后再自己比一次：

# 适用于 Python 3.8+
def index_of(a, x):
i = bisect.bisect_left(a, x)
if i < len(a) and a[i] == x:
return i # 找到了
return -1 # 没找到

print(index_of([10, 20, 30], 20)) # 1
print(index_of([10, 20, 30], 25)) # -1

注意i < len(a)这个判断不能省：如果x比所有元素都大，i会等于len(a)，此时a[i]直接越界。

三、insort：保持有序地插入

insort_left和insort_right（insort是后者的别名）会先二分找位置，再把元素插进去，原地修改列表。

# 适用于 Python 3.8+
import bisect

a = [10, 20, 30]
bisect.insort(a, 25)
print(a) # [10, 20, 25, 30]

b = [10, 20, 20]
bisect.insort_left(b, 20)
print(b) # [10, 20, 20, 20] —— 新元素在最左

要清楚一个复杂度事实：insort里二分是 O(log n)，但插入本身要挪动后段元素，是 O(n)，整体被插入步骤主导。官方文档特别提醒了这一点——所以「频繁插入」的场景，insort未必比别的方法划算，尤其是在链表结构或堆更合适的时候。

四、用插入点反推「最近的值」

bisect天然适合回答「比 x 小的最大元素是哪个」「比 x 大的最小元素是哪个」这类范围查询。官方文档给的五个改造函数里，可以提炼出最常用的两个：

# 适用于 Python 3.8+
import bisect

def find_le(a, x):
"返回 <= x 的最大元素"
i = bisect.bisect_right(a, x)
if i:
return a[i - 1]
raise ValueError("没有 <= x 的元素")

def find_ge(a, x):
"返回 >= x 的最小元素"
i = bisect.bisect_left(a, x)
if i != len(a):
return a[i]
raise ValueError("没有 >= x 的元素")

a = [10, 20, 30, 40]
print(find_le(a, 25)) # 20
print(find_ge(a, 25)) # 30

find_le用的是bisect_right：右插入点的前一个位置，正好是「最后一个 <= x」的元素。find_ge用的是bisect_left：左插入点本身，正好是「第一个 >= x」的元素。

另一个经典用法是分档查表，比如按分数线给等级：

# 适用于 Python 3.8+
import bisect

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

print([grade(s) for s in [59, 70, 90, 100]]) # ['F', 'C', 'A', 'A']

这里的"FDCBA"有 5 个字符，5 个分数段，bisect_right的返回值 0..4 正好当索引。

五、key参数（Python 3.10+）

从Python 3.10起，bisect系列函数新增了key参数，可以在一张「记录表」上按某个字段定位。注意一个细节：key函数只作用于序列里的元素，不作用于被查找的x。

# 适用于 Python 3.10+
import bisect

movies = ["Jaws", "Titanic", "Alien"] # 假设已按 release 年份排序的另一组数据
scores = [(80, "a"), (85, "b"), (90, "c")] # 已按分数升序

# 查找第一个分数 >= 88 的记录
print(bisect.bisect_left(scores, 88, key=lambda r: r[0])) # 2

注意上面x传的是88这个裸数值，因为它不会经过key；而列表元素会被key抽成r[0]。如果写成key=lambda r: r[1]、x又是元组，就很容易对不上。

常见坑点

坑一：把返回值当成「是否找到」。

# 适用于 Python 3.8+
# ❌ 只要值在两元素之间，就会返回一个位置
import bisect
a = [10, 30]
if bisect.bisect_left(a, 20):
print("以为找到了 20") # 会打印，但 20 并不在表里
# ✅ 拿到位置后再比一次
i = bisect.bisect_left(a, 20)
found = i < len(a) and a[i] == 20 # False

坑二：在未排序的列表上用bisect。

# 适用于 Python 3.8+
import bisect

# ❌ bisect 假设序列已升序，乱序结果是未定义的
a = [30, 10, 20]
print(bisect.bisect_left(a, 20)) # 结果没有意义
# ✅ 先排序
a.sort()
print(bisect.bisect_left(a, 20)) # 1

坑三：等值查找时忘了i < len(a)。

# 适用于 Python 3.8+
import bisect

a = [1, 2, 3]
# ❌ x 比所有元素都大时，i == len(a)，a[i] 越界
i = bisect.bisect_left(a, 9)
print(a[i]) # IndexError: list index out of range
# ✅ 先判边界再访问
found = i < len(a) and a[i] == 9 # False

坑四：混用左右，得到不是想要的位置。

# 适用于 Python 3.8+
import bisect

# ❌ 想「插在最右边」却用了 left
a = [20, 20]
bisect.insort_left(a, 20) # [20, 20, 20]，插在最左
# ✅ 想插最右用 insort_right（即 insort）
a = [20, 20]
bisect.insort_right(a, 20) # 插在最右

坑五：以为insort很快。

# 适用于 Python 3.8+
import bisect

data = [5, 3, 8, 1]
# ❌ 以为 insort 整体是 O(log n)；其实插入步骤要挪动后段元素，是 O(n)
keep_sorted = []
for x in data:
bisect.insort(keep_sorted, x) # 每次插入都可能挪动后段
# ✅ 只需要最终有序，批量排一次更直接
print(sorted(data)) # [1, 3, 5, 8]

坑六：key参数用在了 3.10 以下。

# 适用于 Python 3.10+
import bisect
records = [(80, "a"), (90, "b")]

# ❌ 在 3.9 及更早版本里写 key=... 会报 TypeError，别照抄
# bisect.bisect_left(records, 88, key=lambda r: r[0])

# ✅ 3.10+ 直接用 key 参数
print(bisect.bisect_left(records, 88, key=lambda r: r[0])) # 1

# 旧版本替代写法：先抽出键列表，再对键列表二分
keys = [r[0] for r in records]
print(bisect.bisect_left(keys, 88)) # 1

坑七：以为key也会作用到被查找的x。

# 适用于 Python 3.10+
import bisect
records = [(80, "a"), (90, "b")]

# ❌ 让被查找的 x 也变成记录（key 不作用于 x），比较时类型不匹配
print(bisect.bisect_left(records, (88, "?"), key=lambda r: r[0])) # TypeError

# ✅ x 传「可比较的裸值」
print(bisect.bisect_left(records, 88, key=lambda r: r[0])) # 1

总结

用bisect一定要记住两句话：它返回插入点，不返回「找到没找到」；它假设序列已经升序。想拿它做等值查找，就bisect_left得到位置后自己比一次；想做范围查询，就用左右两个插入点去取「相邻的那个元素」。把这两条理顺，bisect就是一把非常顺手的工具。