Python学习总结——二分法

xiaoxiao2021-03-01  30

二分法

引子——练习二分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)]
转载请注明原文地址: https://www.6miu.com/read-4050233.html

最新回复(0)