今天在搜python的redis sorted set实现的时候，发现了一个名叫bisect的模块。 感觉有些意思就介绍下。
该文章写的有些乱，欢迎来喷 ! 另外文章后续不断更新中，请到原文地址查看更新。
大多数要把一组纯数字的列表有序化会直接进行sort()排序，然而有个场景，我们会往列表里不断的插入数据，那么怎么更好的维护列表的有序性？ python中的bisect模块可以向列表中插入元素，同时维护列表的顺序。
bisect的实现也比较简单，大致的原理是首先使用二分查找，查找应该插入的位置，然后用list的insert方法将元素插入到指定的位置。
从理论速度来说，bisect的二分查找速度要快些，但python的sort()是c写的，而bisect排序是纯python写的扩展。
下面是python bisect的使用方法.
#blog: xiaorui.cc In [1]: import bisect In [2]: a = [3,5,6,7,9,21] #查看21应该在那个位置上 In [3]: bisect.bisect(a,22) Out[3]: 6 In [4]: bisect.bisect(a,5) Out[4]: 2 In [5]: bisect.insort(a,1) In [6]: a Out[6]: [1, 3, 5, 6, 7, 9, 21] In [7]: In [7]: bisect. bisect.bisect bisect.bisect_left bisect.bisect_right bisect.insort bisect.insort_left bisect.insort_right
bisect里就四个模块:
bisect_*的函数主要是用来查找插入的位置，insort_*函数是直接将元素放入相应的位置，完成插入。
从bisect模块的实现可以看出，bisect模块中insort函数的插入实现实际上用的就是bisect函数返回的index。
bisect函数返回的index，也可以直接用在list的insert函数中作为插入位置参数。
简单说下二分查找这个算法.
二分查找的对象是：有序数组。这点特别需要注意。要把数组排好序先。
基本步骤：
从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；
如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。
如果在某一步骤数组为空，则代表找不到。
这种搜索算法每一次比较都使搜索范围缩小一半。时间复杂度：O(logn)
下面是bisect实现源码，你会发现他的实现太利索了.
#blog: xiaorui.cc
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)
insort = insort_right # backward compatibility
def bisect_right(a, x, lo=0, hi=None):
"""Return the index where to insert item x in list a, assuming a is sorted.
The return value i is such that all e in a[:i] have e <= x, and all e in
a[i:] have e > x. So if x already appears in the list, a.insert(x) will
insert just after the rightmost x already there.
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
return lo
bisect = bisect_right # backward compatibility
def insort_left(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 left of the leftmost 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 a[mid] < x: lo = mid+1
else: hi = mid
a.insert(lo, x)
def bisect_left(a, x, lo=0, hi=None):
"""Return the index where to insert item x in list a, assuming a is sorted.
The return value i is such that all e in a[:i] have e < x, and all e in
a[i:] have e >= x. So if x already appears in the list, a.insert(x) will
insert just before the leftmost x already there.
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 a[mid] < x: lo = mid+1
else: hi = mid
return lo
# Overwrite above definitions with a fast C implementation
try:
from _bisect import *
except ImportError:
pass
没啥好总结的，用python实现了一遍二分查找算法，话说有些算法长时间不用就忘的干净。
…
