bisect模块的使用

bisect是python内置模块，用于有序序列的插入和查找。

查找 bisect()和bisect_left()

返回合适的插入点索引，使x插入数组a后依然有序。

bisect.bisect(a,x,lo=0 ,hi=len(a),*,key=None) # 等同与bisect_right
bisect.bisect_left(a,x,lo=0 ,hi=len(a),*,key=None)

• a: 有序数组
• x: 查找的数
• lo,hi : 查找范围（a的子集）的上下限
• key: 排序规则，默认直接比较

import bisect
x=3
# x not in a 
a=[0,1,2,4,5]
bisect.bisect_left(a,x) # 3
bisect.bisect(a,x) # 3
# one x in a
a=[0,1,2,3,4,5]
bisect.bisect_left(a,x) # 3
bisect.bisect(a,x) # 4
# many x in a
a=[0,1,2,3,3,3,4,5]
bisect.bisect_left(a,x) # 3
bisect.bisect(a,x) # 6

• bisect()返回值i将a分为两部分：all(val<=x for val in a[lo:i])和all(val>x for val in a[i,hi])
• bisect_left()返回值i将a分为两部分：all(val<x for val in a[lo,i])和all(val>=x for val in a[i,hi])
• 当x不是a中元素时，bisect()和bisect_left()输出是一致的。

#  extract a comparison key from each element in the array
from collections import namedtuple
from operator import attrgetter
from bisect import bisect, insort
from pprint import pprint

Movie = namedtuple('Movie', ('name', 'released', 'director'))

movies = [
   Movie('Jaws', 1975, 'Speilberg'),
   Movie('Titanic', 1997, 'Cameron'),
   Movie('The Birds', 1963, 'Hitchcock'),
   Movie('Aliens', 1986, 'Scott')
]

# Find the first movie released after 1960
by_year = attrgetter('released')
movies.sort(key=by_year)
movies[bisect(movies, 1960, key=by_year)]

# Insert a movie while maintaining sort order
romance = Movie('Love Story', 1970, 'Hiller')
insort(movies, romance, key=by_year)
pprint(movies)

插入 insort()和insort_left()

bisect.insort(a, x, lo=0, hi=len(a), *, key=None)
bisect.insort_left(a, x, lo=0, hi=len(a), *, key=None)

insort()在insect()基础上，将x插入对应的索引；insort_left()和insect_left()类似。