python标准库学习5 ---bisect — Array bisection algorithm

#coding=utf-8

import bisect

list=[1,2,3,4,6,7,8,9]   #假定list已经排序

print bisect.bisect_left(list,5)  #返回5应该插入的索引位置

print bisect.bisect_right(list, 5)

print bisect.bisect(list,5)

bisect.insort_left(list, 5, 0, len(list))

print list

bisect.insort_right(list, 5)

print list

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

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

...     i = bisect(breakpoints, score)

...     return grades[i]

...

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

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

>>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]

>>> data.sort(key=lambda r: r[1])

>>> keys = [r[1] for r in data]         # precomputed list of keys

>>> data[bisect_left(keys, 0)]

('black', 0)

>>> data[bisect_left(keys, 1)]

('blue', 1)

>>> data[bisect_left(keys, 5)]

('red', 5)

>>> data[bisect_left(keys, 8)]

('yellow', 8)