Bisect-Python中的数组二等分算法

就处理器消耗的时间而言，在长列表中的每次插入之后执行排序操作可能会很昂贵。bisect模块可确保列表在插入后仍保持自动排序。为此，它使用二等分算法。该模块具有以下功能：

bisect_left()

此方法在列表中为给定元素定位插入点，以保持排序顺序。如果列表中已经存在该插入点，则该插入点将位于任何现有条目之前（左侧）。返回值可以用作list.insert()的第一个参数

bisect_right()

此方法类似于bisect_left()，但是返回一个插入点，该插入点位于a中x的任何现有条目之后（右侧）。

bisect.insort_left()

此方法按排序顺序插入给定值。这等效于a.insert（bisect.bisect_left(a,x,lo,hi)，x）

bisect.insort_right()

bisect.insort()

两种方法都类似于insort_left()，但是在给定值的任何现有条目之后的列表中插入给定值。

示例

>>> nums = [45,21,34,87,56,12,5,98,30,63]
>>> nums.sort()
>>> nums
[5, 12, 21, 30, 34, 45, 56, 63, 87, 98]
>>> import bisect
>>> p = bisect.bisect_left(nums,50)
>>> p
6
>>> nums.insert(p,50)
>>> nums
[5, 12, 21, 30, 34, 45, 50, 56, 63, 87, 98]
>>> bisect.insort(nums, 29)
>>> nums
[5, 12, 21, 29, 30, 34, 45, 50, 56, 63, 87, 98]