目录

• 简述
• API
  • bisect.bisect_left(a, x, lo=0, hi=len(a))
  • bisect.bisect_right(a, x, lo=0, hi=len(a))
  • bisect.bisect(a, x, lo=0, hi=len(a))
  • bisect.insort_left(a, x, lo=0, hi=len(a))
  • bisect.insort_right(a, x, lo=0, hi=len(a))
  • bisect.insort(a, x, lo=0, hi=len(a))
• 应用

简述

bisect 可用于实现对有序列表中插入元素后,仍然保持列表有序性的功能. 基于二分法( bisection algorithm)算法实现.

Python文档

API

bisect.bisect_left(a, x, lo=0, hi=len(a))

查找元素x在列表a中的左侧插入点(插入点对应列表的下标). 该插入点将原列表分成两部分,左侧所有元素均小于x,右侧所有元素大于等于x.

用Python语言描述的话,可以写成:
all(val < x for val in a[lo:i]) (左侧元素) 或 all(val >= x for val in a[i:hi])(右侧元素)

bisect.bisect_right(a, x, lo=0, hi=len(a))

bisect.bisect(a, x, lo=0, hi=len(a))

查找元素x在列表a中的右侧插入点(插入点对应列表的下标). 该插入点将原列表分成两部分,左侧所有元素均小于等于x,右侧所有元素大于x.

用Python语言描述的话,可以写成:
all(val <= x for val in a[lo:i]) (左侧元素) 或 all(val > x for val in a[i:hi])(右侧元素)

bisect.insort_left(a, x, lo=0, hi=len(a))

将元素x插入到列表a中,同时保持a的顺序性. 如果x已经存在于a,那么在左侧插入.

bisect.insort_right(a, x, lo=0, hi=len(a))

bisect.insort(a, x, lo=0, hi=len(a))

将元素x插入到列表a中,同时保持a的顺序性. 如果x已经存在于a,那么在右侧插入.

具体用法,参考下面示例.

示例

import bisect

# create a sorted list
a = [3, 4, 5, 6, 6, 8, 8]

# search the insert point
x = 6
# since 6 is present in a:
# 1. bisect_left returns insertion point before existing entry. in this case, it returns 3
bisect.bisect_left(a, x)
# 2. bisect_right/bisect returns insertion point after the existing entry. in this case, it returns 5
bisect.bisect(a, x)

# insert x
x = 6
# insort_left insert 6 into position 3. elements a[3:] all moves afterwards.
# after insertion, a = [3, 4, 5, 6, 6, 6, 8, 8]
bisect.insort_left(a, x)

应用

在下面例子中,可以将一个学生的成绩转换成对应的等级.
假设各等级的分数区间分别是[60, 70, 80, 90], 对应的登记分别是['F', 'D', 'C', 'B', 'A'], 利用bisect,可定义如下方法:

def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):
    i = bisect.bisect_left(breakpoints, score)
    return grades[i]

[grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]
# output: ['F', 'A', 'C', 'D', 'B', 'B', 'A']

因为breakpoints中没有重复元素,方法中使用bisect_left或者bisect_right效果一样.