这个模块只有几个函数。
一旦决定使用二分搜索时,立马要想到使用这个模块。
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]