前言二分查找binary search是算法的入门课但 Python 标准库已经把它封装好了——bisect模块。它提供在已排序升序序列上做二分定位和插入的函数。很多人第一次用会踩同一个坑以为bisect返回的是「找到了没有」或者「元素的下标」。都不是。它返回的是一个「插入点」——如果要保持有序新元素应该插在这里。官方文档说得很直接这个模块的函数「设计用来定位插入点」因此它们从不调用__eq__来判断是否找到只用比较返回一个位于两个值之间的插入位置。理解这一点bisect的绝大多数困惑就解开了。本文专讲bisectbisect_left和bisect_rightbisect是后者的别名的区别、insort的插入、在有序序列上的查找以及「怎么用插入点反推出标准的查找结果」。示例以 Python 3.8 为基准key参数需要Python 3.10会单独标注。一、两个核心函数bisect_left与bisect_right签名分别是bisect_left(a, x, lo0, hilen(a), *, keyNone)和bisect_right(a, x, lo0, hilen(a), *, keyNone)。bisect是bisect_right的别名两者完全等价。差别在遇到相等的已有元素时插入点在左边还是右边bisect_left插在已有相等元素之前左。bisect_right插在已有相等元素之后右。# 适用于 Python 3.8import bisecta [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)) # 4bisect 就是 bisect_right对不存在的元素两者返回同一个值# 适用于 Python 3.8print(bisect.bisect_left(a, 25)) # 4print(bisect.bisect_right(a, 25)) # 4官方文档给出的不变式可以帮助记忆bisect_left返回的ip把数组切成两段左段满足所有元素 x右段满足所有元素 xbisect_right则是左段 x、右段 x。二、返回值的意义插入点不是命中这是全篇最该记住的一点。看下面这个容易误用的例子# 适用于 Python 3.8import bisecta [10, 20, 30]i bisect.bisect_left(a, 20)print(i) # 1print(a[i] 20) # True —— 这次碰巧找到了j bisect.bisect_left(a, 25)print(j) # 2print(a[j] 25) # False —— 25 根本不在表里bisect_left对 25 也返回了一个合法位置2但 25 并不存在。所以「返回值」本身不能作为「找到/没找到」的判断依据它只是「如果插入插哪里」。要把它变成真正的等值查找必须拿到位置后再自己比一次# 适用于 Python 3.8def 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)) # 1print(index_of([10, 20, 30], 25)) # -1注意i len(a)这个判断不能省如果x比所有元素都大i会等于len(a)此时a[i]直接越界。三、insort保持有序地插入insort_left和insort_rightinsort是后者的别名会先二分找位置再把元素插进去原地修改列表。# 适用于 Python 3.8import bisecta [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.8import bisectdef 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)) # 20print(find_ge(a, 25)) # 30find_le用的是bisect_right右插入点的前一个位置正好是「最后一个 x」的元素。find_ge用的是bisect_left左插入点本身正好是「第一个 x」的元素。另一个经典用法是分档查表比如按分数线给等级# 适用于 Python 3.8import bisectdef 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.10import bisectmovies [Jaws, Titanic, Alien] # 假设已按 release 年份排序的另一组数据scores [(80, a), (85, b), (90, c)] # 已按分数升序# 查找第一个分数 88 的记录print(bisect.bisect_left(scores, 88, keylambda r: r[0])) # 2注意上面x传的是88这个裸数值因为它不会经过key而列表元素会被key抽成r[0]。如果写成keylambda r: r[1]、x又是元组就很容易对不上。常见坑点坑一把返回值当成「是否找到」。# 适用于 Python 3.8# ❌ 只要值在两元素之间就会返回一个位置import bisecta [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.8import 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.8import bisecta [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.8import bisect# ❌ 想「插在最右边」却用了 lefta [20, 20]bisect.insort_left(a, 20) # [20, 20, 20]插在最左# ✅ 想插最右用 insort_right即 insorta [20, 20]bisect.insort_right(a, 20) # 插在最右坑五以为insort很快。# 适用于 Python 3.8import bisectdata [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.10import bisectrecords [(80, a), (90, b)]# ❌ 在 3.9 及更早版本里写 key... 会报 TypeError别照抄# bisect.bisect_left(records, 88, keylambda r: r[0])# ✅ 3.10 直接用 key 参数print(bisect.bisect_left(records, 88, keylambda r: r[0])) # 1# 旧版本替代写法先抽出键列表再对键列表二分keys [r[0] for r in records]print(bisect.bisect_left(keys, 88)) # 1坑七以为key也会作用到被查找的x。# 适用于 Python 3.10import bisectrecords [(80, a), (90, b)]# ❌ 让被查找的 x 也变成记录key 不作用于 x比较时类型不匹配print(bisect.bisect_left(records, (88, ?), keylambda r: r[0])) # TypeError# ✅ x 传「可比较的裸值」print(bisect.bisect_left(records, 88, keylambda r: r[0])) # 1总结函数返回等值时的位置bisect_left(a, x)插入点已有相等元素之前bisect_right(a, x)插入点已有相等元素之后bisect(a, x)插入点同bisect_rightinsort_left(a, x)None插入到最左insort_right(a, x)None插入到最右用bisect一定要记住两句话它返回插入点不返回「找到没找到」它假设序列已经升序。想拿它做等值查找就bisect_left得到位置后自己比一次想做范围查询就用左右两个插入点去取「相邻的那个元素」。把这两条理顺bisect就是一把非常顺手的工具。