Python中的bisect模块

Python中的bisect模块可以在列表插入元素之后维持列表的有序状态，而不需要重新对列表排序。bisect有以下6个函数，这6个函数接受相同的参数：

• bisect.bisect_left(a, x, lo=0, hi=len(a))：a是列表，x是要插入的元素。函数返回在a中插入x的位置，如果a中已经存x，那么插入的位置在a中最左边的x的前面一位。返回值把列表分成两部分，插入点左侧满足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_left的不同点在于，如果a中已经存x，那么插入的位置在a中最右边的x的后面一位。
• bisect.bisect(a, x, lo=0, hi=len(a))：与bisect.bisect_right相同。返回值把列表分成两部分，插入点左侧满足all(val <= x for val in a[lo:i+1])，插入点右侧满足all(val > x for val in a[i+1:hi])。
• bisect.insort_left(a, x, lo=0, hi=len(a))：返回插入元素后的列表。先使用bisect.bisect_left获得插入元素的位置，然后在该位置插入元素并返回列表。等价于a.insert(bisect.bisect_left(a, x, lo, hi), x)。
• bisect.insort_right(a, x, lo=0, hi=len(a))：等价于a.insert(bisect.bisect_right(a, x, lo, hi), x)。
• bisect.insort(a, x, lo=0, hi=len(a))：等价于a.insert(bisect.bisect(a, x, lo, hi), x)。

举例：

li = [1, 3, 5, 7, 9]
print(bisect.bisect_left(li, 6))
print(bisect.bisect_right(li, 6))
print(bisect.bisect(li, 6))

# Output:
3
3
3

bisect.insort_left(li, 6)
print(li)
bisect.insort_right(li, 4)
print(li)
bisect.insort(li, 8)
print(li)

# Output:
[1, 3, 5, 6, 7, 9]
[1, 3, 4, 5, 6, 7, 9]
[1, 3, 4, 5, 6, 7, 8, 9]

li = [1, 3, 4, 4, 4, 7, 8]
print(bisect.bisect_left(li, 4))
print(bisect.bisect_right(li, 4))
print(bisect.bisect(li, 4))

# Output:
2
5
5

bisect.insort_left(li, 4)
print(li)
bisect.insort_right(li, 4)
print(li)
bisect.insort(li, 4)
print(li)

# Output:
[1, 3, 4, 4, 4, 4, 7, 8]
[1, 3, 4, 4, 4, 4, 4, 7, 8]
[1, 3, 4, 4, 4, 4, 4, 4, 7, 8]