29.1-二分bisect

坚守之心就是不为苦难所惧。苦难是成功的磨刀石，是对人的胆识智慧和毅力的考验。生活的道路不是一帆风顺的，往往荆棘丛生。不少人就是迈不过这道坎，害怕退缩放弃变向，结果只能与成功失之交臂！

二分bisect

二分查找的主要思想是：充分利用数组nums已经排好序的特点，我们取数组nums的中间位置(mid)的元素n_1，用n_1与目标数字x进行比较，如果n_1 等于x，那么直接返回n_1的位置mid；如果n_1大于x，则说明x如果在数组中的话，一定是在n_1的左侧；如果n_1小于x，则说明x如果在数组中的话，一定是在n_1的右侧。

问题1：
有一个无序序列[37,99,73,48,47,40,40,25,99,51],对其先排序输出新列表；
分别尝试插入20,40,41 到这个新序列中合适的位置，保证其有序；

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

一半 一半 一半比较查找；没有距离了，跟边界比较；

# 二分查找实现
def insert_sort(orderlist,i):
    ret = orderlist[:]
    low = 0
    high = len(ret)
    
    while low < high:
        mid = (low+high)//2
        if orderlist[mid] < i:
            low = mid + 1
        else:
            high = mid
    ret.insert(low,i)
    return ret
l = lst
for x in (10,40,100):
    l = insert_sort(l,x)
    print(l)
#---------------------------------------------------
[10, 25, 37, 40, 40, 47, 48, 51, 73, 99, 99]
[10, 25, 37, 40, 40, 40, 47, 48, 51, 73, 99, 99]
[10, 25, 37, 40, 40, 40, 47, 48, 51, 73, 99, 99, 100]

bisect 模块

Python 标准库中有个 bisect 模块是内置模块，它实现了一个算法用于插入元素到有序列表。在一些情况下，这比反复排序列表或构造一个大的列表再排序的效率更高。

bisect 系列 函数可以分2类；
bisect系，用于查找index;
Insort系，用于实际插入；
默认重复时从右边插入；

import bisect
lst = [37,99,73,48,47,40,40,25,99,51]
lst = sorted(lst)
for i,x in enumerate(lst):
    print(i,x)
print('-'*60)

# 二分查找；  查看 插入位置的索引；
x = bisect.bisect(lst,10)  # 插入位置的索引；
print(x)

y = bisect.bisect_left(lst,40)  # 插入处的索引，重复值的时候靠左插入；
print(y)

z = bisect.bisect_right(lst,40)  # 插入处的索引，重复值的时候靠右插入；
print(z)

#将 x 插入到列表 L 中，x 存在时插入在左侧
bisect.insort_left(lst,50)  # 做就地修改， 不推荐；
print(lst)

#将 x 插入到列表 L 中，x 存在时插入在右侧
bisect.insort_right(lst,50)  # 做就地修改， 不推荐；
print(lst)
#------------------------------------------------------------------------------------------------------------------------------
0 25
1 37
2 40
3 40
4 47
5 48
6 51
7 73
8 99
9 99
------------------------------------------------------------
0
2
4
[25, 37, 40, 40, 47, 48, 50, 51, 73, 99, 99]
[25, 37, 40, 40, 47, 48, 50, 50, 51, 73, 99, 99]

二分查找的应用

1. 判断学生成绩，成绩等级A-E。其中，90分以上为‘A’,80-89分为‘B’,70-79分为‘C’,60-69分为‘D’,60分以下为‘E’；

import bisect
def get_grade(score): 
    breakpoints = [60,70,80,90]  # 二分前提是已经排序；
    grades = 'EDCBA'

    return grades[bisect.bisect(breakpoints,score)]
print(get_grade(87))
#-------------------------------------------------------------------------------
B