文章目錄

• ​​二分法與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']