文章目录

二分法与bisect模块二分bisect模块常用函数bisect系，查找indexinsort系，实际插入。 应用

二分法与bisect模块

二分

二分前提是有序，否则不可以二分。二分查找算法的时间复杂度$O({\log }_{2}n)$ 将一个有序序列[37, 99, 73, 48, 47, 40, 40, 25, 99, 51]，对齐先排序输出新的列表。分别尝试插入20,40,41到这个新序列中合适的位置，保证其有序。 思路 排序后二分查找，找到适当位置插入数值。 插入点，使用二分法查找完成。 假设全长为n，首先在大致的中点元素开始和待插入数比较，如果大则和右边的区域的中点继续比较，如果小则和 左边的区域的中点进行比较，以此类推。直到中点就是插入的位置。 算法的核心，就是折半至重合为止。 def insert_sort(orderlist,value): """向有序数组中插入值到对应位置""" ret = orderlist[:] low = 0 high = len(ret) while low < high: mod = (low+high)//2 if value > ret[mod]: low = mod + 1 else: high = mod print(low,high,value) ret.insert(low,value) return ret lst = [37, 99, 73, 48, 47, 40, 40, 25, 99, 51] lst.sort() #升序 print(lst,len(lst)) for i in (40,20,41,100): lst = insert_sort(lst,i) print(lst)

如果是一个比当前有序列表最大值还大的值插入， while low < high 这个条件退出时，就是low等于high，也就 是low可以取到length了，这相当于在尾部追加。原来代码写法只能取到length-1，相当于在最后一个元素的索引 处插入数据，最后一个数据被向后挤。

bisect模块

常用函数

bisect系，查找index

bisect.bisect_left(a, x, lo=0, hi=len(a))->index #查找在有序列a中插入x的index。(如果数组中有多个相同值，索引靠左边)

a #有序列表，必须是升序x #需要插入的值lo 查找的起始范围,默认为0hi 查找的结束范围 默认为len(a)

bisect.bisect_right(a, x, lo=0, hi=len(a))->index #查找在有序列a中插入x的index。(如果数组中有多个相同值，索引靠右边)

bisect.bisect(a, x, lo=0, hi=len(a)) #等价于bisect.bisect_right()

insort系，实际插入。

bisect.insort_left(a, x, lo=0, hi=len(a))->None #在有序列a中插入x元素，直接在原数组中修改。 等同于a.insert(bisect.bisect_left(a,x, lo, hi), x)a #有序列表，必须是升序x #需要插入的值lo 查找的起始范围,默认为0hi 查找的结束范围 默认为len(a) bisect.insort_right(a, x, lo=0, hi=len(a))->None #在有序列a中插入x元素，直接修改原数组。和insort_left函数类似，但如果x已经存在，在其右边插入。bisect.insort(a, x, lo=0, hi=len(a)) #等价于bisect.insort_right

应用

判断学生成绩，成绩等级A_{E。其中，90分以上为’A’，80}89分为’B’，70_{79分为’C’，60}69分 为’D’，60分以下 为’E’

import bisect grade = [60,70,80,90] gradeDict = {0:"E",1:"D",2:'C',3:'B',4:'A'} gradestr = "EDCBA" def showgrade(x:int): # return gradeDict.get(bisect.bisect_right(grade,x)) return gradestr[bisect.bisect_right(grade,x)] for i in (10,60,80,85,100,101): print(i,showgrade(i))

官方示例： >>> 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']