python bisect 模块

python documents 上对于这模块的说明

大致意思就是it uses a basic bisection algorithm，用二分排序算法去维护一个list的有序性。

去看看该模块的实现：

很简单的几个function。 也很好解释

bisect_right 参数(a, x, lo=0, hi=len(a))   第一个为list对象，第二个一个基本对象，它将会在第一个参数list里被比较一次，返回一个可插入点的index。最后两个参数是可选的，用来指定一个list子集的开始和结束点。

insort_right 函数，参数一致。不同之处在于它将比较后的对象插入一个合适的索引位置，也就是list.insert()。python的函数都是引用传值。。

def insort_right(a, x, lo=0, hi=None): """Insert item x in list a, and keep it sorted assuming a is sorted. If x is already in a, insert it to the right of the rightmost x. Optional args lo (default 0) and hi (default len(a)) bound the slice of a to be searched. """ 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 a.insert(lo, x)