python: bisect库

JNingWei

发布于 2018-09-28 14:46:56

7880

发布于 2018-09-28 14:46:56

文章被收录于专栏：JNing的专栏JNing的专栏

介绍

用法

这个模块只有几个函数。

一旦决定使用二分搜索时，立马要想到使用这个模块。

区分

API	父类	定义	是否插入	返回值类型
bisect.bisect_left(L, x)	bisect	在L中查找 x左侧的位置，不存在时返回本该在的位置	否	有
bisect.bisect_right(L, x)	bisect	在L中查找 x右侧的位置，不存在时返回本该在的位置	否	有
bisect.insort_left(L, x=10)	insort	将x 按L顺序插入到列表L中，x存在时插入在左侧	是	无
bisect.insort_right(L, x=10)	insort	将x 按L顺序插入到列表L中，x存在时插入在右侧	是	无

实验代码

# coding=utf-8
import bisect

L = [1, 3, 3, 6, 8, 12, 15]

# 在L中 查找 x左侧的位置
assert bisect.bisect_left(L, x=3) == 1
# 在L中 查找 x右侧的位置，不存在时返回本该在的位置
assert bisect.bisect_right(L, x=3) == 3

# 不存在时返回本该在的位置
assert bisect.bisect_left(L, x=0) == bisect.bisect_right(L, x=0) == 0
assert bisect.bisect_left(L, x=5) == bisect.bisect_right(L, x=5) == 3
assert bisect.bisect_left(L, x=20) == bisect.bisect_right(L, x=20) == 7

# 将x 按L顺序 插入 到列表L中，x存在时插入在左侧
bisect.insort_left(L, x=10)
assert L == [1, 3, 3, 6, 8, 10, 12, 15]
# 将x 按L顺序 插入 到列表L中，x存在时插入在右侧
bisect.insort_right(L, x=10)
assert L == [1, 3, 3, 6, 8, 10, 10, 12, 15]

Ref: python bisect模块使用————二分法

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2017年10月31日，如有侵权请联系 cloudcommunity@tencent.com 删除

python