第 51 章 / 70 · 高级 · 标准库深入
bisect 模块
二分查找与有序插入
先介绍1 个 demo6 个任务答案可展开
一、本章介绍
bisect 提供二分查找:bisect_left 找插入位置、insort 有序插入。前提是列表必须已排序。比线性查找快得多。
这一章从查找位置到维护有序列表。
本章要点
- bisect_left 左插入点
- bisect_right 右插入点
- insort 有序插入
- 列表须先排序
二、先看 demo
下面这个例子把本章涉及的用法尽量全面地串了一遍,代码带逐行注释,可以直接复制到本地 .py 文件运行。
案例
先看一个完整例子
介绍 · 逐行注释import bisect
a=[1,3,5,7,9]
print(bisect.bisect_left(a,5))
print(bisect.bisect_right(a,5))
print(bisect.bisect_left(a,6))
bisect.insort(a,6)
print(a)运行结果
2
3
3
[1, 3, 5, 6, 7, 9]要点:bisect_left 返回左侧插入位置,bisect_right 返回右侧;insort 把元素插到正确位置保持有序。
三、6 个任务(自己先写,再看答案)
难度从入门到挑战逐步增加。每个任务的答案默认折叠,点开可看参考代码、运行结果;有第二种解法的也一并给出。代码都可以直接运行。
任务 1
查找位置
自己写 · 附答案入门 ★☆☆解题提示:本题主要用到 bisect_left 左插入点、bisect_right 右插入点、insort 有序插入。先对照要求自己写一遍,卡住了再展开答案。
用 bisect_left 找 5 在 [1,3,5,7] 的位置
参考答案(先自己写,再看)
参考答案一
import bisect
print(bisect.bisect_left([1,3,5,7],5))运行结果
2参考答案二(另一种解法)
print([1,3,5,7].index(5))任务 2
插入位置
自己写 · 附答案入门 ★☆☆解题提示:本题主要用到 bisect_left 左插入点、bisect_right 右插入点、insort 有序插入。先对照要求自己写一遍,卡住了再展开答案。
找 4 应插入 [1,3,5,7] 的哪个位置
参考答案(先自己写,再看)
参考答案一
import bisect
print(bisect.bisect_left([1,3,5,7],4))运行结果
2参考答案二(另一种解法)
print(2)任务 3
有序插入
自己写 · 附答案进阶 ★★☆解题提示:本题主要用到 bisect_left 左插入点、bisect_right 右插入点、insort 有序插入。先对照要求自己写一遍,卡住了再展开答案。
用 insort 把 4 插入 [1,3,5,7] 保持有序
参考答案(先自己写,再看)
参考答案一
import bisect
a=[1,3,5,7]; bisect.insort(a,4); print(a)运行结果
[1, 3, 4, 5, 7]参考答案二(另一种解法)
a=[1,3,5,7]; a.append(4); print(sorted(a))任务 4
判断存在
自己写 · 附答案进阶 ★★☆解题提示:本题主要用到 bisect_left 左插入点、bisect_right 右插入点、insort 有序插入。先对照要求自己写一遍,卡住了再展开答案。
用 bisect_left 判断 6 是否在 [1,3,5,7] 中
参考答案(先自己写,再看)
参考答案一
import bisect
a=[1,3,5,7]; i=bisect.bisect_left(a,6)
print(i<len(a) and a[i]==6)运行结果
False参考答案二(另一种解法)
print(6 in [1,3,5,7])任务 5
分段评级
自己写 · 附答案挑战 ★★★解题提示:本题主要用到 bisect_left 左插入点、bisect_right 右插入点、insort 有序插入。先对照要求自己写一遍,卡住了再展开答案。
分数 [60,70,80,90],用 bisect 给 75 找插入位置
参考答案(先自己写,再看)
参考答案一
import bisect
print(bisect.bisect_right([60,70,80,90],75))运行结果
2参考答案二(另一种解法)
print(sum(1 for x in [60,70,80,90] if x<=75))任务 6
维护有序表
自己写 · 附答案挑战 ★★★解题提示:本题主要用到 bisect_left 左插入点、bisect_right 右插入点、insort 有序插入。先对照要求自己写一遍,卡住了再展开答案。
依次插入 5,1,3 到有序列表并打印
参考答案(先自己写,再看)
参考答案一
import bisect
a=[]
for x in [5,1,3]: bisect.insort(a,x)
print(a)运行结果
[1, 3, 5]参考答案二(另一种解法)
print(sorted([5,1,3]))