# Python bisect 模块：二分查找的瑞士军刀
先聊点背景。做开发这些年，经常碰到一些场景需要处理有序数据。比如一个排行榜，随时要插入新分数并且保持排序。最早我是用列表加排序，每次插入都调一次sort()，后来发现数据多了就慢得离谱。直到有一天翻标准库发现bisect，算是解决了个大心病。
到底是什么
bisect是Python标准库里的一个模块，翻译过来就是“二分”。说白了，它是在有序序列上做二分查找和插入的工具。注意这个“有序”很关键，它自己不会帮你排序，你得保证操作的对象本身是有序的。
打个比方，就像去图书馆还书。书架上的书已经按照书名拼音排好了，你要把一本书插回正确位置。这时候你不会从头到尾遍历每一本书，而是会先翻到中间，看看目标应该在左边还是右边，然后继续二分。bisect做的就是这事，只不过它是对一个有序列表做这件事。
能解决什么问题
能做的事其实就两个大类：查找位置和插入。
先说查找。有时候你不需要精确知道一个值在不在列表里，只需要知道它应该排在第几个。比如有一个升序列表[1, 3, 5, 7, 9]，想知道4应该插在哪里，bisect_left能告诉你位置2（因为1和3已经占了0和1，4比3大比5小）。bisect_right（或者bisect）则告诉你位置3，表示如果插入重复值，应该放在已有值的后面。
插入就更好理解了。insort其实就是先调bisect找到位置，再调list.insert。组合在一起，就成了一个保持有序的插入操作。
实际开发中，维护有序数据是很常见的需求。比如股票交易系统里维护实时买卖单，或者游戏里处理玩家排行榜，又或者做数据流的中位数计算——这些都是bisect的用武之地。
怎么用起来
用法特别简洁。导入后，主要就是这四个函数：bisect_left、bisect_right、insort_left、insort_right。
importbisect grades=[60,70,80,90]# 找85应该插在哪里position=bisect.bisect_left(grades,85)# 结果是3print(position)# 3，因为85在80和90之间# 直接插入并保持有序bisect.insort(grades,85)print(grades)# [60, 70, 80, 85, 90]有两点值得特别说。bisect_left和bisect_right的区别只在处理重复值时体现。如果列表里有多个相同的值，bisect_left返回最左边的插入位置（保持原顺序），bisect_right返回最右边的。这在实际场景里挺重要，比如做排行榜时同样分数按时间先后排序，用哪个就决定了新成绩排在老成绩前面还是后面。
另外，这些函数都能接受key参数（Python 3.10+），可以自定义比较逻辑。比如有一组学生对象，想按照成绩排序，可以传key=lambda s: s.score。
bisect.insort(student_list,new_student,key=lambdas:s.score)一些使用时的思考
经验教训积累下来，有几个点挺值得注意。
第一，不要对无序数据用bisect。这听起来像废话，但真有人踩过坑。比如从数据库查询数据，有时候排序字段跟bisect用的字段不是同一个，结果就乱套了。保证列表是有序的，并且排序规则跟你插入时用的key是一致的。
第二，性能瓶颈。bisect的查找是O(log n)，非常快。但insort最后一步的list.insert实际上是O(n)的，因为列表是连续存储，插入需要移动后续元素。数据量到了一定规模（比如几十万以上），可以考虑换用更专业的数据结构，比如heapq做优先队列、blist里的sortedlist、或者用bisect配合数组（array模块）在某些场景下也能优化。
第三，有个技巧：如果有一堆数据要批量插入，不要一个一个insort，可以先把所有数据收集起来，一次性排序后合并。这样能利用排序的O(n log n)性能，然后合并有序列表只需要O(n)。Python里heapq.merge就是干这个的。
跟同类技术比一比
对比一下同类方案，能更清楚bisect的定位。
heapq：也是标准库，处理优先队列。它维护的是堆结构，取最小值是O(1)，插入是O(log n)，但无法快速做随机访问。如果你只是需要一个按照某种优先级不断取最小值的场景，heapq比bisect更适合。但如果你需要遍历整个有序列表（比如分页展示排行榜），heapq就力不从心了。
sortedcontainers：第三方库，提供了SortedList、SortedDict等数据结构。它底层用了多种技术（比如跳表或者平衡树），插入、删除、查找都是O(log n)。功能上无疑比bisect强大，但它不是标准库，需要安装依赖。在简单的脚本或者对第三方库有严格限制的环境里，bisect是更稳妥的选择。
纯list+sort()：最直接的做法，每次插入后调sort()。但每次排序都是O(n log n)，n大了就扛不住。想象一下，如果数据有10万条，每插入一条就全排序一次，数据量大了就等着卡死。bisect至少保证了插入前查找是O(log n)，虽然插入本身还是O(n)，但已经比全排序强很多了。
bisect的局限：它只适用于有序列表。如果需要频繁删除中间元素，list删除也是O(n)，这时候用SortedList或者自己实现平衡树结构更合适。另外，bisect不能直接处理多个维度排序——当然，可以通过key函数和元组来间接实现。
总的来说，bisect的设计哲学是“小而美”。它不追求全能，但它在自己擅长的领域里（维护有序列表）表现得足够好。如果你的场景就是需要在一个有序列表里频繁查找插入位置，而且数据量还没大到让O(n)的插入成为瓶颈，用bisect是很好的选择。如果性能要求更高或者功能更复杂，再考虑其他方案也不迟。
