Python in a Nutshell, 2nd Edition

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

bisect(seq,item,lo=0,hi=None) 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 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 is faster if len(seq) is large. You may pass optional arguments lo and hi to operate on the slice seq[lo:hi].

insort

insort(seq,item,lo=0,hi=None) Like seq.insert(bisect(seq,item),item). In other words, seq must be a sorted mutable sequence (usually a sorted list), 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.