8.6 The bisect Module
The bisect module uses a
bisection algorithm to keep a list in sorted order as items are
inserted. bisect's operation is
faster than calling a list's sort
method after each insertion. This section documents the main
functions supplied by bisect.
bisect(seq,item,lo=0,hi=sys.maxint)
|
|
Returns the index i into
seq where item
should be inserted to keep seq sorted. In
other words, i is such that each item in
seq[:i]
is less than or equal to item, and each
item in
seq[i:]
is greater than or equal to item.
seq must be a sorted sequence. For any
sorted sequence seq,
seq[bisect(seq,y)-1]=
=y is equivalent to
y in
seq, but faster if
len(seq)
is large. You may pass optional arguments
lo and hi to
operate on the slice
seq[lo:hi].
insort(seq,item,lo=0,hi=sys.maxint)
|
|
Like
seq.insert(bisect(seq,item),item).
In other words, seq must be a sorted
mutable sequence, and insort modifies
seq by inserting
item at the right spot, so that
seq remains sorted. You may pass optional
arguments lo and
hi to operate on the slice
seq[lo:hi].
Module bisect also supplies functions
bisect_left, bisect_right,
insort_left, and insort_right
for explicit control of search and insertion strategies into
sequences that contain duplicates. bisect is a
synonym for bisect_right, and
insort is a synonym for
insort_right.
|