二分查找算法实现的python bisect有序队列

今天在搜python的redis sorted set实现的时候,发现了一个名叫bisect的模块。  感觉有些意思就介绍下。 

该文章写的有些乱,欢迎来喷 ! 另外文章后续不断更新中,请到原文地址查看更新。

http://xiaorui.cc/2016/03/01/%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE%E7%AE%97%E6%B3%95%E5%AE%9E%E7%8E%B0%E7%9A%84python-bisect%E6%9C%89%E5%BA%8F%E9%98%9F%E5%88%97/

大多数要把一组纯数字的列表有序化会直接进行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实现了一遍二分查找算法,话说有些算法长时间不用就忘的干净。


大家觉得文章对你有些作用! 如果想赏钱,可以用微信扫描下面的二维码,感谢!
另外再次标注博客原地址  xiaorui.cc

发表评论

电子邮件地址不会被公开。 必填项已用*标注