python bisect_python bisect

Python的bisect模块，用于维护有序列表。bisect模块实现了将元素插入一个有序序列的算法，它利用二分算法实现排序，相比于每次调用sort而言，这样无疑要高效许多。bisect_*系列方法用于求索引，insort_*系列方法用于有序插入

1. 常用方法

I. bisect.bisect_left(a, x, lo=0, hi=len(a))

a是一个有序列表，x是插入其中的元素， lo和hi分别代表列表的切片索引(默认为0和列表长度)

此方法用于寻找一个保证插入元素后列表仍然有序的索引值。当元素x插入a列表后列表仍保持有序状态，且当列表内已经有与x值相同的元素时，x会插入到其中所有相同元素的最左边，方法会返回所插入元素在列表中的索引，并保证在索引值左边的元素都比所插入元素小，右边的都不比所插入元素大(大于等于)

import bisect

if __name__ == ‘__main__’:

l = [1, 2, 3, 4]

k = []

print(bisect.bisect_left(l, 3))

print(bisect.bisect_left(k, 2))

>>> 2

>>> 0

II. bisect.bisect_right、bisect.bisect

这两种都方法和bisect_left类似，唯一的区别就是出现相同元素会优先向右边插入，同样是返回索引值。

import bisect

if __name__ == ‘__main__’:

l = [1, 2, 3, 4]

k = [1, 2, 3, 3, 3, 4]

print(bisect.bisect_right(l, 3))

print(bisect.bisect_right(k, 3))

print(bisect.bisect(l, 3))

print(bisect.bisect(k, 3))

>>> 3

>>> 5

>>> 3

>>> 5

III. bisect.insort_left(a, x, lo=0, hi=len(a))

不破壞 a 的排序的情况下下插入x， 和 a.insert(bisect.bisect_left(a,x, lo, hi), x) 的效果相同。搜寻只需要 O(log n)时间而插入需要很慢的 O(n)时间，这使得插入操作主导了需要花费的时间。

if __name__ == ‘__main__’:

l = [1, 2, 3, 4]

k = [1, 2, 3, 3, 3, 4]

bisect.insort_right(l, 3)

print(l)

l.insert(bisect.bisect_right(l, 3), 3)

print(l)

>>> [1, 2, 3, 3, 4]

>>> [1, 2, 3, 3, 3, 4]

IV. bisect.insort_right(a,x, lo=0, hi=len(a))、 bisect.insort(a, x,lo=0, hi=len(a))

与insort_left用法类似，区别在于对于重复的值会执行右插，插入的位置在所有a列表中的x的后面(右边)

if __name__ == ‘__main__’:

l = [1, 2, 3, 4]

k = [1, 2, 3, 3, 3, 4]

bisect.insort_right(l, 3)

print(l)

l.insert(bisect.bisect_right(l, 3), 3)

print(l)

>>> [1, 2, 3, 3, 4]

>>> [1, 2, 3, 3, 3, 4]

2. 二分查找

前文说到过二分查找，二分查找也称折半查找(Binary Search)，它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。每次查询会将表分为两部分，然后对于符合要求的那一部分继续执行同上所述的查找流程，直至无法再细分子表。

I.表必须采用顺序存储结构

II.必须按关键字大小有序排列

我们也可以自己来实现一下二分查找方法，虽然效率上会低于bisect

I. 循环实现

def binary_search_by_cycle(lst, item, start, end):

while start <= end:

mid = (start + end) // 2

if lst[mid] == item:

return mid

elif lst[mid] < item:

start = mid + 1

else:

end = mid – 1

return None

if __name__ == ‘__main__’:

l = [i for i in range(1, 10000, 2)]

print(binary_search_by_cycle(l, 9979, 0, len(l)))

>>> 4989

II. 递归实现

def binary_search_by_recursion(lst, item, start, end):

if start > end:

return None

mid = (start + end) // 2

if lst[mid] < item:

return binary_search_by_recursion(lst, item, mid+1, end)

elif lst[mid] > item:

return binary_search_by_recursion(lst, item, start, mid-1)

else:

return mid

if __name__ == ‘__main__’:

l = [i for i in range(1, 10000, 2)]

print(binary_search_by_recursion(l, 9979, 0, len(l)))

>>> 4989