【Python】 —— Bisect模块学习笔记

Bisect模块学习笔记

说明以及功能

简单说明：bisect模块使用了二分法的基本算法，是Python中针对有序数组在插入新数据仍然保持有序的一种方法

import bisect
# 导入模块

具体功能：

1. bisect()函数

（1）bisect_left()函数

• 其目的在于查找数值 x 将会插入的位置并返回，但不会插入原数组。
• 如果x存在在a中则返回x左边的位置

bisect.bisect_left(a, x, lo=0, hi=len(a))
'''  
     a 原列表
     x 插入的元素
     lo 起始位置 默认值为0
     hi 结束位置 默认值为len(a)
'''
# 例子
a = [1,2,4,5,6,8,9,10]

# 如果a不存在x，则仅返回将会插入的位置
print(bisect.bisect_left(a,7))
# 如果 x 已经在 a 里存在，那么插入点会在已存在元素之前（也就是左边）
print(bisect.bisect_left(a,2))

----------------------------------------------------------------
# 结果
>>> 5  如果a不存在x，则仅返回将会插入的位置
>>> 1  如果 x 已经在 a 里存在，那么插入点会在已存在元素之前（也就是左边）

bisect_left()函数源代码：

def bisect_left(a, x, lo=0, hi=None):
    # 如果起始位置小于0 则报错,即列表为空
    if lo < 0:
        raise ValueError('lo must be non-negative')
    # 如果没有指定的结束位置则默认为列表的长度
    if hi is None:
        hi = len(a)
    # 二分法算法
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] < x: lo = mid+1
        else: hi = mid
    # 返回位置
    return lo

（2）bisect.bisect_right()和bisect.bisect()

• bisect.bisect()功能与bisect.bisect_right()完全一样 bisect = bisect_right # backward compatibility
• 内容跟 bisect.bisect_left() 一样，但如果x存在在a中则返回x左边的位置

bisect.bisect_right(a, x, lo=0, hi=len(a))
bisect.bisect(a, x, lo=0, hi=len(a))
'''  
     a 原列表
     x 插入的元素
     lo 起始位置 默认值为0
     hi 结束位置 默认值为len(a)
'''

# 例子
# 如果a不存在x，则仅返回将会插入的位置
print(bisect.bisect_right(a,7))
# print(bisect.bisect(a,7))

# 如果 x 已经在 a 里存在，那么插入点会在已存在元素之后（也就是右边）
print(bisect.bisect_right(a,2))
# print(bisect.bisect(a,2))
----------------------------------------------------------------
# 结果
>>> 5  如果a不存在x，则仅返回将会插入的位置
>>> 2  如果 x 已经在 a 里存在，那么插入点会在已存在元素之后（也就是右边）

bisect.bisect_right()源代码：

def bisect_right(a, x, lo=0, hi=None):
    # 如果起始位置小于0 则报错,即列表为空
    if lo < 0:
        raise ValueError('lo must be non-negative')
    # 如果没有指定的结束位置则默认为列表的长度
    if hi is None:
        hi = len(a)
    # 二分法算法
    while lo < hi:
        mid = (lo+hi)//2
        if x < a[mid]: hi = mid
        else: lo = mid+1
    # 返回位置
    return lo

2. insort()函数

（1） bisect.insort_left()函数

• 在有序列表a中插入元素x，如果a存在相同元素x，把它插入相同元素的前边即左边

bisect.insort_left(a, x, lo=0, hi=len(a))
'''  
     a 原列表
     x 插入的元素
     lo 起始位置 默认值为0
     hi 结束位置 默认值为len(a)
'''

# 例子
a = [1,2,4,5,6,8,9,10]

# 如果a不存在x，则返回插入的位置
bisect.insort_left(a,7)
print(a)
# 如果a存在相同元素x，把它插入相同元素的前边即左边
bisect.insort_left(a,2.0)
print(a)

----------------------------------------------------------------
# 结果
[1, 2, 4, 5, 6, 7, 8, 9, 10]   如果a不存在x，则返回插入的位置
[1, 2.0, 2, 4, 5, 6, 7, 8, 9, 10]  如果a存在相同元素x，把它插入相同元素的前边即左边

insort_left()函数源代码：

def insort_left(a, x, lo=0, hi=None):
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] < x: lo = mid+1
        else: hi = mid
    # 前面部分与bisect_left()相同，差别在于最后一步是插入
    # 插入
    a.insert(lo, x)

（2） insort_right()函数和insort()函数

• insort()函数的功能与insort_roght()函数一样insort = insort_right # backward compatibility
• 在列表a中插入元素x，如果a存在相同元素x，把它插入相同元素的前边即右边

bisect.insort_right(a, x, lo=0, hi=len(a))
# bisect.insort(a, x, lo=0, hi=len(a))
'''  
     a 原列表
     x 插入的元素
     lo 起始位置 默认值为0
     hi 结束位置 默认值为len(a)
'''

# 例子
a = [1,2,4,5,6,8,9,10]

# 如果a不存在x，则返回插入的位置
bisect.insort_right(a,7)
# bisect.insort(a,7)
print(a)
# 如果a存在相同元素x，把它插入相同元素的前边即左边
bisect.insort_right(a,2.0)
bisect.insort(a,2.0)
print(a)

----------------------------------------------------------------
# 结果
[1, 2, 4, 5, 6, 7, 8, 9, 10] 如果a不存在x，则返回插入的位置
[1, 2, 2.0, 2.0, 4, 5, 6, 7, 8, 9, 10] 如果a存在相同元素x，把它插入相同元素的前边即左边

insort_right()函数源代码：

def insort_right(a, x, lo=0, hi=None):
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x < a[mid]: hi = mid
        else: lo = mid+1
    # 前面部分与bisect_right()相同，差别在于最后一步是插入
    # 插入
    a.insert(lo, x)
   

参考资料

参考链接：官方文档：https://docs.python.org/zh-cn/3/library/bisect.html
源代码：https://github.com/python/cpython/blob/3.10/Lib/bisect.py