用bisect来管理已排序的序列

引入：

你正在维持一个有序列表，如年级成绩列表[已经按照从小到大排序]，现在要录入一个新同学的成绩，那么我们如何找到插入的位置。

比较合理的方法是使用二分查找，对于这一类的情况，最好是使用Python内置的bisect模块。

bisect 模块包含两个主要函数，bisect 和 insort，两个函数都利用二分查找算法来在 有序序列中查找或插入元素。

一、使用bisect查找

bisect(nums:list,target,lo=None, hi=None)

查找目标target在排序列表中的插入位置[插入后仍然保持升序]

• nums 有序列表
• target 查找目标
• lo 指定查找位置的起点
• hi指定查找位置的终点

import bisect

if __name__ == '__main__':
    nums = [1, 3, 5, 7, 9, 10, 11, 13, 15, ]

    target1 = 10
    index1 = bisect.bisect(nums, target1)
    print(index1)  # 6

    target2 = 6
    index2 = bisect.bisect(nums, target2)
    print(index2)  # 3

如果我们的列表中只有一部分是有序的，则可以使用lo,hi

import bisect

if __name__ == '__main__':
    # 前 7 位代表特殊含义，不参与排序
    nums = [-1, 0, -1, 0, -1, 0, -1, 0, 1, 3, 5, 7, 9, 10, 11, 13, 15, ]

    target1 = 10
    index = bisect.bisect(nums, target1, 7)
    print(index)  # 14

    nums.insert(index, 10)
    print(nums)  # [-1, 0, -1, 0, -1, 0, -1, 0, 1, 3, 5, 7, 9, 10, 10, 11, 13, 15]

二、使用insort插入

insort(nums:list,target,lo=None, hi=None)

将目标target在排序列表中插入[插入后仍然保持升序]，比bisect + insert效率更高。

• nums 有序列表
• target 查找目标
• lo 指定起点
• hi指定终点

import bisect

if __name__ == '__main__':
    nums = [1, 3, 5, 7, 9, 10, 11, 13, 15, ]

    bisect.insort(nums, 4)
    print(nums)  # [1, 3, 4, 5, 7, 9, 10, 11, 13, 15]

    bisect.insort(nums, 10)
    print(nums)  # [1, 3, 4, 5, 7, 9, 10, 10, 11, 13, 15]