| % LaTeX produced by Fred L. Drake, Jr. <fdrake@acm.org>, with an |
| % example based on the PyModules FAQ entry by Aaron Watters |
| % <arw@pythonpros.com>. |
| |
| \section{\module{bisect} --- |
| Array bisection algorithms for binary searching.} |
| \declaremodule{standard}{bisect} |
| |
| \modulesynopsis{Array bisection algorithms for binary searching.} |
| |
| |
| |
| This module provides support for maintaining a list in sorted order |
| without having to sort the list after each insertion. For long lists |
| of items with expensive comparison operations, this can be an |
| improvement over the more common approach. The module is called |
| \module{bisect} because it uses a basic bisection algorithm to do its |
| work. The source code may be most useful as a working example of the |
| algorithm (i.e., the boundary conditions are already right!). |
| |
| The following functions are provided: |
| |
| \begin{funcdesc}{bisect}{list, item\optional{, lo\optional{, hi}}} |
| Locate the proper insertion point for \var{item} in \var{list} to |
| maintain sorted order. The parameters \var{lo} and \var{hi} may be |
| used to specify a subset of the list which should be considered. The |
| return value is suitable for use as the first parameter to |
| \code{\var{list}.insert()}. |
| \end{funcdesc} |
| |
| \begin{funcdesc}{insort}{list, item\optional{, lo\optional{, hi}}} |
| Insert \var{item} in \var{list} in sorted order. This is equivalent |
| to \code{\var{list}.insert(bisect.bisect(\var{list}, \var{item}, |
| \var{lo}, \var{hi}), \var{item})}. |
| \end{funcdesc} |
| |
| |
| \subsection{Example} |
| \nodename{bisect-example} |
| |
| The \function{bisect()} function is generally useful for categorizing |
| numeric data. This example uses \function{bisect()} 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..84 is a `B', etc. |
| |
| \begin{verbatim} |
| >>> grades = "FEDCBA" |
| >>> breakpoints = [30, 44, 66, 75, 85] |
| >>> from bisect import bisect |
| >>> def grade(total): |
| ... return grades[bisect(breakpoints, total)] |
| ... |
| >>> grade(66) |
| 'C' |
| >>> map(grade, [33, 99, 77, 44, 12, 88]) |
| ['E', 'A', 'B', 'D', 'F', 'A'] |
| \end{verbatim} |