python函数--bisect 二分查找模块_bisect查找指定范围

bisect 模块包含两个主要函数， bisect 和 insort两个函数都利用二分查找算法来在有序序列中查找或插入元素
bisect 查找 查找的意思是函数的返回值是位置并非真的把数字插入到序列中
备注：bisect.bisect_left(a, x, lo=0, hi=len(a))
第1个参数表示查找的有序列表(无序的不行，要先排序)，第2个参数表示待查找的目标值，第3、4个参数表示列表中查找的范围，不写默认是查找的是列表的整个范围
或者直接只写两个参数：
bisect(haystack,needle)在haystack（干草垛）里搜索 needle（针）的位置，该位置满足的条件是，把 needle 插入这个位置之后， haystack 还能保持升序。也就是在说这个函数返回的位置前面的值，都小于或等于 needle 的值

import bisect
a = [0, 1, 5, 7, 19, 25]
a1 = bisect.bisect(a, 6)

# 这里返回的位置是3是因为：
# 为了保证插入这个数，还能保持列表升序，这个位置显而易见就在值5后面
print(a1)#3
1
2
3
4
5
6
7

bisect 函数其实是 bisect_right 函数的别名，后者还有个姊妹函数叫bisect_left。
bisect_left函数是新元素会被放置于它相等的元素的前面即左边，而 bisect_right返回的则是跟它相等的元素之后的位置即右边

import bisect
a = [0, 4, 5, 7, 19, 25]
# a[2]=5，表示值5的索引位置是2
# 这个返回3，是因为bisect会把新的元素放在相等元素后面即 2 + 1 = 3
a1 = bisect.bisect(a, 5)
# 这个返回2，是因为bisect_left会把新的元素放在相等元素前面即原来值5的索引位置2
a2 = bisect.bisect_left(a, 5)
print(a1, a2) # 3, 2
1
2
3
4
5
6
7
8

bisect 可以用来建立一个用数字作为索引的查询表格：

def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):
    i = bisect.bisect(breakpoints, score)
    print("i is:",i)
    print("breakpoints is:",breakpoints)#打印为breakpoints is: [60, 70, 80, 90]因为bisect是查找功能并非插入功能
    return grades[i]

print([grade(score) for score in [33, 99, 77, 70, 89, 90, 100]])#['F', 'A', 'C', 'C', 'B', 'A', 'A']
1
2
3
4
5
6
7

对于33来说，通过bisect返回的位置是0，所以对应的grades值是[0]=F
对于99来说，通过bitsect返回的位置是3，所以对应的grades值是[3]=B
insort 插入
insort(seq, item) 把变量 item 插入到序列 seq 中，并能保持 seq 的升序顺序

import random
import bisect

my_list = []
for i in range(10):
    new_item = random.randrange(20)#rand范围是20以内
    bisect.insort(my_list, new_item)#把随机生的数据插入到list中
print(my_list)

a = [1, 2, 3, 3, 6, 9, 10, 20]
# 往列表a插入一个数字3并且使得列表有序
bisect.insort_left(a, 3)#[1, 2, 3, 3, 3, 6, 9, 10, 20]
print(a)
# 往列表a插入一个数字3并且使得列表有序
bisect.insort_right(a, 4)
print(a)#[1, 2, 3, 3, 3, 4, 6, 9, 10, 20]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

—本博文为转发并调试