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.