This module provides support for maintaining a list in sorted order withouthaving to sort the list after each insertion. For long lists of items withexpensive comparison operations, this can be an improvement over the more commonapproach. The module is calledbisect because it uses a basic bisectionalgorithm to do its work. The source code may be most useful as a workingexample of the algorithm (the boundary conditions are already right!).
The following functions are provided:
Locate the proper insertion point foritem inlist to maintain sorted order.The parameterslo andhi may be used to specify a subset of the list whichshould be considered; by default the entire list is used. Ifitem is alreadypresent inlist, the insertion point will be before (to the left of) anyexisting entries. The return value is suitable for use as the first parametertolist.insert(). This assumes thatlist is already sorted.
New in version 2.1.
Similar tobisect_left(), but returns an insertion point which comes after(to the right of) any existing entries ofitem inlist.
New in version 2.1.
Insertitem inlist in sorted order. This is equivalent tolist.insert(bisect.bisect_left(list,item,lo,hi),item). This assumesthatlist is already sorted.
New in version 2.1.
Similar toinsort_left(), but insertingitem inlist after anyexisting entries ofitem.
New in version 2.1.
Thebisect() function is generally useful for categorizing numeric data.This example usesbisect() to look up a letter grade for an exam total(say) based on a set of ordered numeric breakpoints: 85 and up is an ‘A’, 75..84is a ‘B’, etc.
>>>grades="FEDCBA">>>breakpoints=[30,44,66,75,85]>>>frombisectimportbisect>>>defgrade(total):...returngrades[bisect(breakpoints,total)]...>>>grade(66)'C'>>>map(grade,[33,99,77,44,12,88])['E', 'A', 'B', 'D', 'F', 'A']
array — Efficient arrays of numeric values
