| 1 | \section{\module{bisect} ---
|
|---|
| 2 | Array bisection algorithm}
|
|---|
| 3 |
|
|---|
| 4 | \declaremodule{standard}{bisect}
|
|---|
| 5 | \modulesynopsis{Array bisection algorithms for binary searching.}
|
|---|
| 6 | \sectionauthor{Fred L. Drake, Jr.}{[email protected]}
|
|---|
| 7 | % LaTeX produced by Fred L. Drake, Jr. <[email protected]>, with an
|
|---|
| 8 | % example based on the PyModules FAQ entry by Aaron Watters
|
|---|
| 9 | % <[email protected]>.
|
|---|
| 10 |
|
|---|
| 11 |
|
|---|
| 12 | This module provides support for maintaining a list in sorted order
|
|---|
| 13 | without having to sort the list after each insertion. For long lists
|
|---|
| 14 | of items with expensive comparison operations, this can be an
|
|---|
| 15 | improvement over the more common approach. The module is called
|
|---|
| 16 | \module{bisect} because it uses a basic bisection algorithm to do its
|
|---|
| 17 | work. The source code may be most useful as a working example of the
|
|---|
| 18 | algorithm (the boundary conditions are already right!).
|
|---|
| 19 |
|
|---|
| 20 | The following functions are provided:
|
|---|
| 21 |
|
|---|
| 22 | \begin{funcdesc}{bisect_left}{list, item\optional{, lo\optional{, hi}}}
|
|---|
| 23 | Locate the proper insertion point for \var{item} in \var{list} to
|
|---|
| 24 | maintain sorted order. The parameters \var{lo} and \var{hi} may be
|
|---|
| 25 | used to specify a subset of the list which should be considered; by
|
|---|
| 26 | default the entire list is used. If \var{item} is already present
|
|---|
| 27 | in \var{list}, the insertion point will be before (to the left of)
|
|---|
| 28 | any existing entries. The return value is suitable for use as the
|
|---|
|
|---|
