目录/第 51 章 · bisect 模块
第 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] 的位置

我的代码草稿(可复制到本地 .py 文件运行)
参考答案(先自己写,再看)
参考答案一
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] 的哪个位置

我的代码草稿(可复制到本地 .py 文件运行)
参考答案(先自己写,再看)
参考答案一
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] 保持有序

我的代码草稿(可复制到本地 .py 文件运行)
参考答案(先自己写,再看)
参考答案一
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] 中

我的代码草稿(可复制到本地 .py 文件运行)
参考答案(先自己写,再看)
参考答案一
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 找插入位置

我的代码草稿(可复制到本地 .py 文件运行)
参考答案(先自己写,再看)
参考答案一
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 到有序列表并打印

我的代码草稿(可复制到本地 .py 文件运行)
参考答案(先自己写,再看)
参考答案一
import bisect
a=[]
for x in [5,1,3]: bisect.insort(a,x)
print(a)
运行结果
[1, 3, 5]
参考答案二(另一种解法)
print(sorted([5,1,3]))