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