• 博客访问： 657466
• 博文数量： 87
• 博客积分： 0
• 博客等级： 民兵
• 技术积分： 2022
• 用 户 组： 普通用户
• 注册时间： 2014-04-23 11:16

2015年（47）

2014年（40）

2015-06-09 19:08:19

bisect模块可以使列表保持已排好的顺序，使用二分算法。

bisect(list,item,[low,[high]])                返回要插入item点的索引，如果item在列表中了，则返回该条目的右边索引
bisect_right(list,iten,[left,[right]])        同上
bisect_left(list,iten,[left,[right]])          返回要插入item点的索引，如果item在列表中了，则返回该条目的左边索引
insort(list,item,[left,[right]])                不返回索引，直接插入进去，如果有重复的item，则插入到右边
insort_right(list,item,[left,[right]])       同上
insort_left(list,item,[left,[right]])         不返回索引，直接插入进去，如果有重复的item，则插入到左边

1. """Bisection algorithms."""

2. def insort_right(a, x, lo=0, hi=None):
3.     """Insert item x in list a, and keep it sorted assuming a is sorted.

4.     If x is already in a, insert it to the right of the rightmost x.

5.     Optional args lo (default 0) and hi (default len(a)) bound the
6.     slice of a to be searched.
7.     """

8.     if lo < 0:
9.         raise ValueError('lo must be non-negative')
10.     if hi is None:
11.         hi = len(a)
12.     while lo < hi:
13.         mid = (lo+hi)//2
14.         if x < a[mid]: hi = mid
15.         else: lo = mid+1
16.     a.insert(lo, x)

17. insort = insort_right # backward compatibility

18. def bisect_right(a, x, lo=0, hi=None):
19.     """Return the index where to insert item x in list a, assuming a is sorted.

20.     The return value i is such that all e in a[:i] have e <= x, and all e in
21.     a[i:] have e > x. So if x already appears in the list, a.insert(x) will
22.     insert just after the rightmost x already there.

23.     Optional args lo (default 0) and hi (default len(a)) bound the
24.     slice of a to be searched.
25.     """

26.     if lo < 0:
27.         raise ValueError('lo must be non-negative')
28.     if hi is None:
29.         hi = len(a)
30.     while lo < hi:
31.         mid = (lo+hi)//2
32.         if x < a[mid]: hi = mid
33.         else: lo = mid+1
34.     return lo

35. bisect = bisect_right # backward compatibility

36. def insort_left(a, x, lo=0, hi=None):
37.     """Insert item x in list a, and keep it sorted assuming a is sorted.

38.     If x is already in a, insert it to the left of the leftmost x.

39.     Optional args lo (default 0) and hi (default len(a)) bound the
40.     slice of a to be searched.
41.     """

42.     if lo < 0:
43.         raise ValueError('lo must be non-negative')
44.     if hi is None:
45.         hi = len(a)
46.     while lo < hi:
47.         mid = (lo+hi)//2
48.         if a[mid] < x: lo = mid+1
49.         else: hi = mid
50.     a.insert(lo, x)

51. def bisect_left(a, x, lo=0, hi=None):
52.     """Return the index where to insert item x in list a, assuming a is sorted.

53.     The return value i is such that all e in a[:i] have e < x, and all e in
54.     a[i:] have e >= x. So if x already appears in the list, a.insert(x) will
55.     insert just before the leftmost x already there.

56.     Optional args lo (default 0) and hi (default len(a)) bound the
57.     slice of a to be searched.
58.     """

59.     if lo < 0:
60.         raise ValueError('lo must be non-negative')
61.     if hi is None:
62.         hi = len(a)
63.     while lo < hi:
64.         mid = (lo+hi)//2
65.         if a[mid] < x: lo = mid+1
66.         else: hi = mid
67.     return lo

68. # Overwrite above definitions with a fast C implementation
69. try:
70.     from _bisect import bisect_right, bisect_left, insort_left, insort_right, insort, bisect
71. except ImportError:
72.     pass