二分法与bisect模块

淡淡的烟草味﹌ 2022-01-28 08:41 189阅读 0赞

### 文章目录 ###

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

# 二分法与bisect模块 #

## 二分 ##

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

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)

![bisect\_001][bisect_001]  
如果是一个比当前有序列表最大值还大的值插入， 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

## 应用 ##

判断学生成绩，成绩等级AE。其中，90分以上为’A’，8089分为’B’，7079分为’C’，6069分 为’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))

![bisect\_002][bisect_002]

*  官方示例：

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

[bisect_001]: /images/20220128/7b3f344018de434fa031ac6dba3247ac.png
[bisect_002]: /images/20220128/bae2f0a9eb224bca93f16582afb67af5.png