python标准库学习—bisect模块

bisect模块可以使列表保持已排好的顺序，使用二分算法。bisect(list,item,[low,[high]])                返回要插入item点的索引，如果item在列表中了，则返回该条目的右边索引bisect_right(list,iten,[left,[right]])        同上bisect_left(list,iten,[left,[right]])          返回要插入item点的索引，如果item在列表中了，则返回该条目的左边索引insort(list,item,[left,[right]])                不返回索引，直接插入进去，如果有重复的item，则插入到右边insort_right(list,item,[left,[right]])       同上insort_left(list,item,[left,[right]])         不返回索引，直接插入进去，如果有重复的item，则插入到左边下面是整个模块在linux python2.6版本的源码："""Bisection algorithms."""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 compatibilitydef 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    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 lobisect = bisect_right # backward compatibilitydef 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    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 implementationtry:    from _bisect import bisect_right, bisect_left, insort_left, insort_right, insort, bisectexcept ImportError:    pass