相关博文
- ·
- ·
- ·
- ·
- ·
- ·
- ·
- ·
- ·
- ·
分类： python/ruby
2015-06-09 19:08:19
bisect模块可以使列表保持已排好的顺序，使用二分算法。
bisect(list,item,[low,[high]]) 返回要插入item点的索引，如果item在列表中了，则返回该条目的右边索引
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，则插入到左边
下面是整个模块在linux python2.6版本的源码：
下面是整个模块在linux python2.6版本的源码：
-
"""bisection algorithms."""
-
-
def insort_right(a, x, lo=0, hi=none):
-
"""insert item x in list a, and keep it sorted assuming a is sorted.
-
-
if x is already in a, insert it to the right of the rightmost x.
-
-
optional args lo (default 0) and hi (default len(a)) bound the
-
slice of a to be searched.
-
"""
-
-
if lo < 0:
-
raise valueerror('lo must be non-negative')
-
if hi is none:
-
hi = len(a)
-
while lo < hi:
-
mid = (lohi)//2
-
if x < a[mid]: hi = mid
-
else: lo = mid1
-
a.insert(lo, x)
-
-
insort = insort_right # backward compatibility
-
-
def bisect_right(a, x, lo=0, hi=none):
-
"""return the index where to insert item x in list a, assuming a is sorted.
-
-
the return value i is such that all e in a[:i] have e <= x, and all e in
-
a[i:] have e > x. so if x already appears in the list, a.insert(x) will
-
insert just after the rightmost x already there.
-
-
optional args lo (default 0) and hi (default len(a)) bound the
-
slice of a to be searched.
-
"""
-
-
if lo < 0:
-
raise valueerror('lo must be non-negative')
-
if hi is none:
-
hi = len(a)
-
while lo < hi:
-
mid = (lohi)//2
-
if x < a[mid]: hi = mid
-
else: lo = mid1
-
return lo
-
-
bisect = bisect_right # backward compatibility
-
-
def insort_left(a, x, lo=0, hi=none):
-
"""insert item x in list a, and keep it sorted assuming a is sorted.
-
-
if x is already in a, insert it to the left of the leftmost x.
-
-
optional args lo (default 0) and hi (default len(a)) bound the
-
slice of a to be searched.
-
"""
-
-
if lo < 0:
-
raise valueerror('lo must be non-negative')
-
if hi is none:
-
hi = len(a)
-
while lo < hi:
-
mid = (lohi)//2
-
if a[mid] < x: lo = mid1
-
else: hi = mid
-
a.insert(lo, x)
-
-
-
def bisect_left(a, x, lo=0, hi=none):
-
"""return the index where to insert item x in list a, assuming a is sorted.
-
-
the return value i is such that all e in a[:i] have e < x, and all e in
-
a[i:] have e >= x. so if x already appears in the list, a.insert(x) will
-
insert just before the leftmost x already there.
-
-
optional args lo (default 0) and hi (default len(a)) bound the
-
slice of a to be searched.
-
"""
-
-
if lo < 0:
-
raise valueerror('lo must be non-negative')
-
if hi is none:
-
hi = len(a)
-
while lo < hi:
-
mid = (lohi)//2
-
if a[mid] < x: lo = mid1
-
else: hi = mid
-
return lo
-
-
# overwrite above definitions with a fast c implementation
-
try:
-
from _bisect import bisect_right, bisect_left, insort_left, insort_right, insort, bisect
-
except importerror:
- pass
给主人留下些什么吧！~~