Georg Brandl | 116aa62 | 2007-08-15 14:28:22 +0000 | [diff] [blame^] | 1 | |
| 2 | :mod:`bisect` --- Array bisection algorithm |
| 3 | =========================================== |
| 4 | |
| 5 | .. module:: bisect |
| 6 | :synopsis: Array bisection algorithms for binary searching. |
| 7 | .. sectionauthor:: Fred L. Drake, Jr. <fdrake@acm.org> |
| 8 | |
| 9 | |
| 10 | .. % LaTeX produced by Fred L. Drake, Jr. <fdrake@acm.org>, with an |
| 11 | .. % example based on the PyModules FAQ entry by Aaron Watters |
| 12 | .. % <arw@pythonpros.com>. |
| 13 | |
| 14 | This module provides support for maintaining a list in sorted order without |
| 15 | having to sort the list after each insertion. For long lists of items with |
| 16 | expensive comparison operations, this can be an improvement over the more common |
| 17 | approach. The module is called :mod:`bisect` because it uses a basic bisection |
| 18 | algorithm to do its work. The source code may be most useful as a working |
| 19 | example of the algorithm (the boundary conditions are already right!). |
| 20 | |
| 21 | The following functions are provided: |
| 22 | |
| 23 | |
| 24 | .. function:: bisect_left(list, item[, lo[, hi]]) |
| 25 | |
| 26 | Locate the proper insertion point for *item* in *list* to maintain sorted order. |
| 27 | The parameters *lo* and *hi* may be used to specify a subset of the list which |
| 28 | should be considered; by default the entire list is used. If *item* is already |
| 29 | present in *list*, the insertion point will be before (to the left of) any |
| 30 | existing entries. The return value is suitable for use as the first parameter |
| 31 | to ``list.insert()``. This assumes that *list* is already sorted. |
| 32 | |
| 33 | .. versionadded:: 2.1 |
| 34 | |
| 35 | |
| 36 | .. function:: bisect_right(list, item[, lo[, hi]]) |
| 37 | |
| 38 | Similar to :func:`bisect_left`, but returns an insertion point which comes after |
| 39 | (to the right of) any existing entries of *item* in *list*. |
| 40 | |
| 41 | .. versionadded:: 2.1 |
| 42 | |
| 43 | |
| 44 | .. function:: bisect(...) |
| 45 | |
| 46 | Alias for :func:`bisect_right`. |
| 47 | |
| 48 | |
| 49 | .. function:: insort_left(list, item[, lo[, hi]]) |
| 50 | |
| 51 | Insert *item* in *list* in sorted order. This is equivalent to |
| 52 | ``list.insert(bisect.bisect_left(list, item, lo, hi), item)``. This assumes |
| 53 | that *list* is already sorted. |
| 54 | |
| 55 | .. versionadded:: 2.1 |
| 56 | |
| 57 | |
| 58 | .. function:: insort_right(list, item[, lo[, hi]]) |
| 59 | |
| 60 | Similar to :func:`insort_left`, but inserting *item* in *list* after any |
| 61 | existing entries of *item*. |
| 62 | |
| 63 | .. versionadded:: 2.1 |
| 64 | |
| 65 | |
| 66 | .. function:: insort(...) |
| 67 | |
| 68 | Alias for :func:`insort_right`. |
| 69 | |
| 70 | |
| 71 | Examples |
| 72 | -------- |
| 73 | |
| 74 | .. _bisect-example: |
| 75 | |
| 76 | The :func:`bisect` function is generally useful for categorizing numeric data. |
| 77 | This example uses :func:`bisect` to look up a letter grade for an exam total |
| 78 | (say) based on a set of ordered numeric breakpoints: 85 and up is an 'A', 75..84 |
| 79 | is a 'B', etc. :: |
| 80 | |
| 81 | >>> grades = "FEDCBA" |
| 82 | >>> breakpoints = [30, 44, 66, 75, 85] |
| 83 | >>> from bisect import bisect |
| 84 | >>> def grade(total): |
| 85 | ... return grades[bisect(breakpoints, total)] |
| 86 | ... |
| 87 | >>> grade(66) |
| 88 | 'C' |
| 89 | >>> map(grade, [33, 99, 77, 44, 12, 88]) |
| 90 | ['E', 'A', 'B', 'D', 'F', 'A'] |
| 91 | |
| 92 | |