bisect数组的二分算法

本模块实现已经排序的队列列表插入元素之后保持排序。对于个大量数据的列表来看，插入元素并保持排序，计算量是非常大的。本模块实现了bisect算法，主要基于二分算法来实现。

bisect.bisect_left(a, x, lo=0, hi=len(a)) 

对有序列表a里插入元素x，保持有序不变，返回插入的位置。参数lo和hi是表示判断列表的范围，默认是整个范围。如果插入的元素x已经在列表a存在，那就插入在存在元素的左边。

例子：

#Python 3.4

import bisect

l = [8, 5, 6, 6, 3]

l.sort()

print(l)

print(bisect.bisect_left(l, 0))

print(l)

print(bisect.bisect_left(l, 5))

print(bisect.bisect_left(l, 7))

结果输出如下：

[3, 5, 6, 6, 8]

0

[3, 5, 6, 6, 8]

1

4

bisect.bisect_right(a, x, lo=0, hi=len(a)) 

bisect.bisect(a, x, lo=0, hi=len(a)) 

在有序队列a里查找x可以插入的位置，并保持队列有序。如果插入的值与队列里的值相同，则插入在相同元素的右边，把这个位置的索引值返回。

例子：

#python 3.4

TWE-Commerce

一个功能强大的B2B与B2C的购物平台，除了原本OSC功能外，增加更新的功能： 一、 取消了register_globals必须开启的限制 二、 將HTML程式碼与PHP程式碼完全分离，採用了smarty 樣板引擎 三、 每支档案includes所需函数与资料库连结，使的网页显示速度明显提升 四、 检视、购买商品群组权限设定 五、 十八岁以下禁购机制 六、 折价券购物抵扣机制 七、 礼券购物机制

0

查看详情

import bisect

l = [8, 5, 6, 6, 3]

l.sort()

print(l)

print(bisect.bisect_right(l, 0))

print(l)

print(bisect.bisect(l, 5))

print(bisect.bisect(l, 7))

结果输出如下：

[3, 5, 6, 6, 8]

0

[3, 5, 6, 6, 8]

2

4

bisect.insort_left(a, x, lo=0, hi=len(a)) 

插入一个元素x到队列a，并把把队列排序。要当于：a.insert(bisect.bisect_left(a, x, lo, hi), x)。

例子：

#python 3.4

import bisect

l = [8, 5, 6, 6, 3]

l.sort()

print(l)

bisect.insort_left(l, 0)

print(l)

bisect.insort_left(l, 5)

print(l)

bisect.insort_left(l, 7)

print(l)

结果输出如下：

[3, 5, 6, 6, 8]

[0, 3, 5, 6, 6, 8]

[0, 3, 5, 5, 6, 6, 8]

[0, 3, 5, 5, 6, 6, 7, 8]

bisect.insort_right(a, x, lo=0, hi=len(a)) 

bisect.insort(a, x, lo=0, hi=len(a)) 

插入元素x到a队列里，如果发现有相同元素，就插入到相同元素的右边。

例子：

#python 3.4

import bisect

l = [8, 5, 6, 6, 3]

l.sort()

print(l)

bisect.insort_right(l, 0)

print(l)

bisect.insort(l, 5)

print(l)

bisect.insort(l, 7)

print(l)

结果输出如下：

[3, 5, 6, 6, 8]

[0, 3, 5, 6, 6, 8]

[0, 3, 5, 5, 6, 6, 8]

[0, 3, 5, 5, 6, 6, 7, 8]

使用上面的函数进行一些简单的封装：

def index(a, x):

    'Locate the leftmost value exactly equal to x'

    i = bisect_left(a, x)

    if i != len(a) and a[i] == x:

        return i

    raise ValueError

def find_lt(a, x):

    'Find rightmost value less than x'

    i = bisect_left(a, x)

    if i:

        return a[i-1]

    raise ValueError

def find_le(a, x):

    'Find rightmost value less than or equal to x'

    i = bisect_right(a, x)

    if i:

        return a[i-1]

    raise ValueError

def find_gt(a, x):

    'Find leftmost value greater than x'

    i = bisect_right(a, x)

    if i != len(a):

        return a[i]

    raise ValueError

def find_ge(a, x):

    'Find leftmost item greater than or equal to x'

    i = bisect_left(a, x)

    if i != len(a):

        return a[i]

    raise ValueError

使用来对学生成绩转换为ABCDF等级：

#python 3.4

import bisect

def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):

     i = bisect.bisect(breakpoints, score)

     return grades[i]

print([33, 99, 77, 70, 89, 90, 100])

print([grade(score) for score in [33, 99, 77, 70, 89, 90, 100]])

结果输出如下：

[33, 99, 77, 70, 89, 90, 100]

['F', 'A', 'C', 'C', 'B', 'A', 'A']