二分法

引子——练习二分bisect模块bisect.bisect_left(a,x, lo=0, hi=len(a))bisect.bisect_right(a,x, lo=0, hi=len(a)) 或 bisect.bisect(a, x,lo=0, hi=len(a))bisect.insort_left(a,x, lo=0, hi=len(a))bisect.insort_right(a,x, lo=0, hi=len(a)) 或者 bisect.insort(a, x,lo=0, hi=len(a)) 应用

引子——练习

有一个无序序列[37, 99, 73, 48, 47, 40, 40, 25, 99, 51]，对其先排序输出新列表。 分别尝试插入20、40、41到这个新序列中合适的位置，保证其有序。 def insert_sort(orderlist, i): ret = orderlist[:] low = 0 high = len(ret) # 因为有整除，所以去掉减1，不影响整除2，但影响下一行判断。防止大于所有数的插入有问题 while low < high: # 如果改为<= ，虽然最大数能满足 ，但最小数会出现死循环问题 mid = (low+high) // 2 if i > orderlist[mid]: low = mid + 1 else: high = mid ret.insert(low,i) return ret

二分

二分前提是有序，否则不可以二分。二分查找算法的时间复杂度O(log n)

bisect模块

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

查找在有序列表a中插入x的index。lo和hi用于指定列表的区间，默认是使用整个列表。如果x已经存在，在其左边插入。返回值为index。

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

和bisect_left类似，但如果x已经存在，在其右边插入。

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

在有序列表a中插入x。等同于a.insert(bisect.bisect_left(a,x, lo, hi), x) 。

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

和insort_left函数类似，但如果x已经存在，在其右边插入。

应用

判断学生成绩，成绩等级A~E。其中，90分以上为’A’ , 80~89分为’B’ , 70~79分为’C’ , 60~69分为’D’, 60分一下为 ‘E’ 。 import bisect def scores(score): lst = [60,70,80,90] clas = 'EDCBA' return clas[bisect.bisect(lst,score)]