二分插入、bisect

在一个有序序列（从小到大）中查找一个元素

每次将元素与序列中间位置的元素进行比较

如果大于中点，则在后半段。如果小于中点，则在前半段。以此类推

时间复杂度为O(logn)

有一个无序序列[37, 99, 73, 48, 47, 40, 40, 25, 99, 51]，对其先排序输出新列表。

分别插入20、40、41、100到这个新序列中合适的位置，保证其有序。

origin = [37, 99, 73, 48, 47, 40, 40, 25, 99, 51]

origin = sorted(origin)

# print(origin)

# [25, 37, 40, 40, 47, 48, 51, 73, 99, 99]

# 有重复时从左边插入

def insert_sort(origin:list, num):

	low = 0

	high = len(origin)

	while low < high:

		mid = (low + high)//2

		# 如果大于中点，则在后半部分

		if num > origin[mid]:

			low = mid + 1

		# 否则在前半部分

		else:

			high = mid

	origin.insert(low, num)

for num in (20, 40, 41, 100):

	insert_sort(origin, num)

print(origin)

# [20, 25, 37, 40, 40, 40, 41, 47, 48, 51, 73, 99, 99, 100]

origin = [37, 99, 73, 48, 47, 40, 40, 25, 99, 51]

origin = sorted(origin)

# 有重复时从右边插入

def insert_sort(origin:list, num):

	low = 0

	high = len(origin)

	while low < high:

		mid = (low + high)//2

		if num < origin[mid]:

			high = mid

		else:

			low = mid + 1

	origin.insert(low, num)

for num in (20, 40, 41, 100):

	insert_sort(origin, num)

print(origin)

# [20, 25, 37, 40, 40, 40, 41, 47, 48, 51, 73, 99, 99, 100]

---

bisect模块

bisect包含两个主要函数 bisect和insort，都是基于二分法实现

• bisect: bisect_right的别名，返回插入点位置，有重复时返回右边插入点
• bisect_left: 返回插入点位置，有重复时返回左边插入点
• insort: insort_right的别名，默认有重复时从右边插入
• insort_left: 有重复时从左边插入

import bisect

origin = [37, 99, 73, 48, 47, 40, 40, 25, 99, 51]

origin = sorted(origin)

for num in (20, 40, 41, 100):

	bisect.insort_left(origin, num)

print(origin)

# [20, 25, 37, 40, 40, 40, 41, 47, 48, 51, 73, 99, 99, 100]

判断学生成绩，成绩等级A-E，其中，90分以上为A，80-89为B，70-79为C，60-69为D，50-59为E

breakpoints = [60, 70, 80, 90]

grades = 'EDCBA'

index = bisect.bisect(breakpoints, 55)

print(grades[index])

# E

参考：

https://zh.wikipedia.org/wiki/二分搜索算法

https://docs.python.org/3/library/bisect.html