Python bisect模块的使用与源码分析

本文基于Python3.7分析

1. 模块简介

• bisect模块属于Python内置模块
• 内部核心算法是二分法
• 用于操作的列表必须是升序的(空列表也可以)
• 功能: 在保证原有顺序的情况下, 插入一个元素(或返回元素如果插入的下标值),不影响原有顺序

2. 源码分析及使用

2.1. 方法概述

bisect提供了六个方法:

• 查找: 返回元素按照顺序应该插入的位置, 但不会修改原列表

  方法	解释
  bisect.bisect()	遇到重复值时,按照最右边返回
  bisect.bisect_left()	遇到重复值时,按照最左边返回
  bisect.bisect_right()	遇到重复值时,按照最右边返回

• 插入: 将元素插入到列表中, 不影响原有顺序

  方法	解释
  bisect.insort()	遇到重复值, 插入到最右边
  bisect.insort_left()	遇到重复值, 插入到最左边
  bisect.insort_right()	遇到重复值, 插入到最右边

不难发现, bisect()方法和bisect_right()方法以及insort()方法和insort_right()方法功能一致, 在下面源码分析中会有解释

2.2. 使用

import bisect

l = [1, 2, 4, 4, 5]
n = 4

idx1 = bisect.bisect(l, n)
print(idx1)
# 4

idx2 = bisect.bisect_left(l, n)
print(idx2)
# 2

idx3 = bisect.bisect_right(l, n)
print(idx3)
# 4

bisect.insort(l, n)
# bisect.insort_left(l, n)
# bisect.insort_right(l, n)
print(l)
# [1, 2, 4, 4, 4, 5]

2.3. 源码分析

def bisect_left(a, x, lo=0, hi=None):
    """
    	假设对a排序, 返回将x插入到a中的索引值i, 当遇到重复值时, 按照最左边位置返回
    	使得a[:i]中所有元素都小于x
    	
    	a: list, 假设已经排好序的列表(升序)
    	x: 需要插入的元素
    	lo=0: 二分算法中的low指针位置, 默认0
    	hi=None: 二分算法中的high指针位置, 默认None, 表示len(a)
    """

    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


def bisect_right(a, x, lo=0, hi=None):
    """
    	假设对a排序, 返回将x插入到a中的索引值i, 当遇到重复值时, 按照最右边位置返回
    	使得a[:i]中所有元素都小于等于x
    """

    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

   
def insort_left(a, x, lo=0, hi=None):
    """
    	将x插入到列表a中, 不影响a原有顺序(假设a升序排列), 当遇到重复值时, 插入到最左边
    """

    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
    a.insert(lo, x)

   
def insort_right(a, x, lo=0, hi=None):
    """
    	将x插入到列表a中, 不影响a原有顺序(假设a升序排列), 当遇到重复值时, 插入到最右边
    """

    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
    a.insert(lo, x)

bisect()和bisect_right()以及insort()和insort_right()功能相同的原因:
在源码的最下面存在这样两句代码:

# Create aliases
bisect = bisect_right
insort = insort_right

所以bisect就是bisect_right方法的一个引用, 可是说是别名, 同理insort是insert_right方法的引用

本文地址：https://blog.csdn.net/ww08153115/article/details/107282894