文章目录

• ​​二分法与bisect模块​​

• ​​二分​​
• ​​bisect模块​​

• ​​常用函数​​

• ​​bisect系，查找index​​
• ​​insort系，实际插入。​​

• ​​应用​​

二分法与bisect模块

二分

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

1. 将一个有序序列[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 查找的起始范围,默认为0
• hi 查找的结束范围 默认为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 查找的起始范围,默认为0
• hi 查找的结束范围 默认为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

应用

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']