导读：算法是程序的灵魂，而复杂度则是算法的核心指标之一。为了降低复杂度量级，可谓是令无数程序员绞尽脑汁、甚至是摧枯秀发。一般而言，若能实现对数阶的时间复杂度，算法效率往往就已经非常理想。而实现对数阶的常用思想莫过于二分。
二分常有，好用的二分并不常有。while条件是lo<hi还是lo<=hi？分支判断mid是+1还是-1还是仍然取值mid？最后return哪个值？如果目标序列不是严格递增又该怎么处理？想想都不禁让人敬而远之。幸运的是，在python语言中，已经内置了成熟的二分函数。
看完本文，二分不再是空中楼阁，而会"真香"
01 初识bisect
bisect.py是一个独立的模块文件，默认存放在安装目录下的Lib文件夹中(例如：..\Python\Python37\Lib)，整个代码实现非常简单，仅仅是定义了4个函数(算上等价的是6个)，共计不到100行。
主要实现了二分查找和二分插入两项大的功能，为了兼顾目标序列非严格递增的情形（即允许有重复值），查找和插入又都区分是左查找还是右查找、左插入还是右插入。
默认情况下是右查找和右插入。
02 方法示例
应用二分法主要有两种情形：一种是将目标元素插入到已知有序列表中，另一种是在有序列表中查找目标元素索引。
首先来看二分插入。bisect模块提供了两种插入方式，主要是考虑兼容目标列表不是严格递增的情况，其中：
- insort_right：右插入，即将目标元素插入到尽可能靠右的位置，当在列表中遇到等值目标元素时，会继续向右探索，直至小于右边元素的位置才插入
- insort_left：左插入，与右插入相反，即当存在重复元素时，尽可能靠左地插入至列表
- insort：完全等价于insort_right
- 除了列表和待插入元素外，还支持两个缺省参数lo和hi，其中lo默认为0，hi默认为列表长度，区间是左闭右开，即[lo, hi)
- 当限定了目标区间后，则元素只在指定区间进行比较，并插入到最右或者最左端，而不管区间外元素的大小
看个示例会更加清楚：
from bisect import * lyst = [1, 3, 3, 5, 7] insort_left(lyst, 3) print(lyst) #[1, 3, 3, 3, 5, 7] insort_right(lyst, 4, 0, 3) #指定lo=0, hi=3 print(lyst) #[1, 3, 3, 4, 3, 5, 7]，因为限定区间，所以插入了错误位置
对于纯数字列表而言，插入本无左右之分
再看返回索引的二分查找。提供了两种返回索引的原则，即最左索引还是最右索引：
- bisect_right：返回尽可能靠右的插入目标元素索引，保证返回索引位置满足：右侧的元素都严格大于目标元素，左侧元素小于或者等于目标元素
- bisect_left：与前者相反，会返回尽可能靠左的插入目标元素索引
- bisect：完全等价于bisect_right
- 特殊情况下，当目标元素比列表中所有元素都大时，返回len(lyst)；反之，当目标元素比列表中所有元素都小时，返回索引0
from bisect import * lyst = [1, 3, 3, 5, 7] index = bisect_right(lyst, 3) print(index) #index = 3，存在重复元素，靠右插入 index = bisect_right(lyst, 6, lo=0, hi=3) print(index) #index = 3，限定插入区间后，仅在该区间比对，返回index有误 index = bisect_left(lyst, 3) print(index) #index = 1，存在重复元素，靠左插入 index = bisect_left(lyst, 9) print(index) #index = len(lyst) = 5 index = bisect_left(lyst, 0) print(index) #index = 0
03 改造重写
Python内置的二分法虽然好用，但不得不说功能还是太单一了。都是插入函数，它能用于原原本本的二分查找吗，带返回-1那种？不能。除了单列表类型，还能用于其他数据结构吗？好像也不行。但我们可以对其稍微进行改造，以实现更多个性化的二分函数。
- 鉴于字符串具有比较操作，bisect天然支持字符串列表的插入和查找
from bisect import * strs = ['ab', 'cd', 'ef', 'gh'] insort(strs, 'cd') print(strs) # ['ab', 'cd', 'cd', 'ef', 'gh'] str_ = 'abcefg'#因字符串不可原地更改，仅支持查找索引而不能插入 index = bisect(str_, 'b') print(index) # index = 2
- 稍加改造，也能实现原原本本的二分查找
from bisect import * lyst = [1, 3, 3, 5, 7] tmp = bisect(lyst, 4) index = tmp if tmp>0 and lyst[tmp-1] == 4 else -1 print(index) #查找元素不存在，返回index = -1 tmp = bisect(lyst, 3) index = tmp if tmp>0 and lyst[tmp-1] == 3 else -1 print(index) #查找元素存在，返回靠右的元素索引index = 3 #bisect = bisect_right，所以与左侧值比较是否存在目标元素；若想返回靠左索引，可类似改造bisect_left
- 参照内置函数，改写比较方法，可实现定制的二分法
"""内置bisect函数 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 x < a[mid]: hi = mid else: lo = mid+1 return lo """ def my_bisect_right(a, x, lo=0, hi=None): """ x元素数据结构形如（'A', 19） a是x类元素的列表，根据x中的数值变量排序 函数计划返回靠右的插入索引 """ 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 x[1] < a[mid][1]: hi = mid###仅改写此行比较方法即可实现定制 else: lo = mid+1 return lo lyst = [('A', 19), ('B', 20), ('C', 20), ('D', 22)] x = ('X', 20) index = my_bisect_right(lyst, x) print(index) #index = 3
04 效率测试按照bisect文档说明，内置二分法函数用C语言重写以实现效率上提高，我们原原本本copy一个内置函数的实现，用作效率对比。
from bisect import bisect_right ###直接copy内置函数实现的my_bisect_right，用作对比 def my_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 x < a[mid]: hi = mid else: lo = mid+1 return lo from time import time lyst = list(range(10**6))#有序列表长度为100万 start = time() for _ in range(10**6):#二分效率太高，所以重复100万次 index = my_bisect_right(lyst, 100) print('my_bisect_right time used: ', time()-start) #my_bisect_right time used: 2.959082841873169 start = time() for _ in range(10**6): index = bisect_right(lyst, 100) print('built-in bisect_right time used: ', time()-start) #built-in bisect_right time used: 0.5924952030181885
可见，内置的二分函数经过C语言重写，确实在效率上要高于自定义的纯python函数，大概是5倍的差距。所以在使用二分法时可优先考虑内置函数。
05 总结
- python内置bisect模块提供了常用的二分操作，而且用C语言重写，相比自定义的二分函数有一定性能提升
- 模块提供了有限的函数接口，但可轻松实现定制化的改造重写
- 从编程实现上，内置函数写法简洁高效、足够pythonic，当疲于处理二分边界条件和返回值时，不妨参考一下官方写法
- 内置的二分虽好用，但真正理解并随时会写好二分更重要
