python基础 有序序列 二分查找 bisect

 1 import bisect
 2 """
 3 bisect.bisect_left(a, x, lo=0, hi=len(a))
 4 在 a 中找到 x 合适的插入点以维持有序。参数 lo 和 hi 可以被用于确定需要考虑的子集；默认情况下整个列表都会被使用。如果 x 已经在 a 里存在，那么插入点会在已存在元素之前（也就是左边）。如果 a 是列表（list）的话，返回值是可以被放在 list.insert() 的第一个参数的。
 5 返回的插入点 i 可以将数组 a 分成两部分。左侧是 all(val < x for val in a[lo:i]) ，右侧是 all(val >= x for val in a[i:hi]) 。bisect_right与其类似
 6 """
 7 list_orderd = [1, 2, 3, 4, 7, 9, 10, 10, 22, 45]
 8 list_normal = [1, 2, 99, 34, 3, 7, 5, 7, 4, 2]
 9 print(bisect.bisect_left(list_orderd, 8), list_orderd) #5 [1, 2, 3, 4, 7, 9, 10, 10, 22, 45] 返回8插入的索引值，如果list_order里面已经有8则返回其左边的索引值，源列表不会变化
10 print(bisect.bisect_left(list_normal, 8), list_normal)#10 [1, 2, 99, 34, 3, 7, 5, 7, 4, 2] 由于bisect使用二分法查找，其前提是序列本身有序，如对无序序列使用此方法结果将不可预期
11 
12 """
13 bisect.insort_left(a, x, lo=0, hi=len(a))
14 将 x 插入到一个有序序列 a 里，并维持其有序。如果 a 有序的话，这相当于 a.insert(bisect.bisect_left(a, x, lo, hi), x)。要注意搜索是 O(log n) 的，插入却是 O(n) 的;right方法类似
15 """
16 print(bisect.insort_left(list_orderd, 8), list_orderd) #None [1, 2, 3, 4, 7, 8, 9, 10, 10, 22, 45] 该方法返回值为None,直接修改源列表
17 
18 #对于无序序列可以使用sort方法对其进行排序，排序以后就可以使用bisect方法了,sort方法使用
19 list_normal.sort()
20 print(list_normal) #[1, 2, 2, 3, 4, 5, 7, 7, 34, 99]
21 
22 data = [(‘red‘, 5), (‘blue‘, 1), (‘yellow‘, 8), (‘black‘, 0)]
23 data.sort(key=lambda r: r[1])
24 print(data) #有规律的嵌套容器类型排序方法
25 keys = [r[1] for r in data]
26 print(keys) #[0, 1, 5, 8] 可以对此序列使用bisect方法
27 
28 #bisect还能用于数字表的查询，示例如下。从一个给定的考试成绩集合里，通过一个有序数字表，查出其对应的字母等级：90 分及以上是 ‘A‘，80 到 89 是 ‘B‘，以此类推
29 def grade(score, breakpoints=[60, 70, 80, 90], grades=‘FDCBA‘):
30     i = bisect.bisect(breakpoints, score)
31     return grades[i]
32 print([grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]) #[‘F‘, ‘A‘, ‘C‘, ‘C‘, ‘B‘, ‘A‘, ‘A‘]
33 
34 """
35 利用下面函数可以将bisect利用修改为查找元素大小的函数
36 def index(a, x):
37     ‘Locate the leftmost value exactly equal to x‘
38     i = bisect_left(a, x)
39     if i != len(a) and a[i] == x:
40         return i
41     raise ValueError
42 
43 def find_lt(a, x):
44     ‘Find rightmost value less than x‘
45     i = bisect_left(a, x)
46     if i:
47         return a[i-1]
48     raise ValueError
49 
50 def find_le(a, x):
51     ‘Find rightmost value less than or equal to x‘
52     i = bisect_right(a, x)
53     if i:
54         return a[i-1]
55     raise ValueError
56 
57 def find_gt(a, x):
58     ‘Find leftmost value greater than x‘
59     i = bisect_right(a, x)
60     if i != len(a):
61         return a[i]
62     raise ValueError
63 
64 def find_ge(a, x):
65     ‘Find leftmost item greater than or equal to x‘
66     i = bisect_left(a, x)
67     if i != len(a):
68         return a[i]
69     raise ValueError
70 """