Mercurial > cpython-lru_cache-weakref

annotate Doc/library/bisect.rst @ 54294:dba767bc3155 legacy-trunk

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
remove mention of old ctypes version
author Benjamin Peterson <benjamin@python.org>
date Sat, 23 May 2009 20:59:09 +0000
parents 31cf38bdaac0
children 9ee9e7aa8abc
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
42604
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
1
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
2 :mod:`bisect` --- Array bisection algorithm
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
3 ===========================================
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
4
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
5 .. module:: bisect
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
6 :synopsis: Array bisection algorithms for binary searching.
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
7 .. sectionauthor:: Fred L. Drake, Jr. <fdrake@acm.org>
44383
3625234bf3d2 Some cleanup in the docs.
Georg Brandl <georg@python.org>
parents: 42604
diff changeset
8 .. example based on the PyModules FAQ entry by Aaron Watters <arw@pythonpros.com>
42604
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
9
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
10 This module provides support for maintaining a list in sorted order without
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
11 having to sort the list after each insertion. For long lists of items with
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
12 expensive comparison operations, this can be an improvement over the more common
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
13 approach. The module is called :mod:`bisect` because it uses a basic bisection
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
14 algorithm to do its work. The source code may be most useful as a working
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
15 example of the algorithm (the boundary conditions are already right!).
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
16
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
17 The following functions are provided:
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
18
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
19
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
20 .. function:: bisect_left(list, item[, lo[, hi]])
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
21
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
22 Locate the proper insertion point for *item* in *list* to maintain sorted order.
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
23 The parameters *lo* and *hi* may be used to specify a subset of the list which
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
24 should be considered; by default the entire list is used. If *item* is already
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
25 present in *list*, the insertion point will be before (to the left of) any
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
26 existing entries. The return value is suitable for use as the first parameter
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
27 to ``list.insert()``. This assumes that *list* is already sorted.
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
28
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
29 .. versionadded:: 2.1
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
30
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
31
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
32 .. function:: bisect_right(list, item[, lo[, hi]])
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
33
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
34 Similar to :func:`bisect_left`, but returns an insertion point which comes after
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
35 (to the right of) any existing entries of *item* in *list*.
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
36
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
37 .. versionadded:: 2.1
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
38
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
39
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
40 .. function:: bisect(...)
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
41
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
42 Alias for :func:`bisect_right`.
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
43
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
44
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
45 .. function:: insort_left(list, item[, lo[, hi]])
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
46
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
47 Insert *item* in *list* in sorted order. This is equivalent to
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
48 ``list.insert(bisect.bisect_left(list, item, lo, hi), item)``. This assumes
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
49 that *list* is already sorted.
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
50
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
51 .. versionadded:: 2.1
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
52
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
53
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
54 .. function:: insort_right(list, item[, lo[, hi]])
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
55
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
56 Similar to :func:`insort_left`, but inserting *item* in *list* after any
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
57 existing entries of *item*.
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
58
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
59 .. versionadded:: 2.1
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
60
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
61
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
62 .. function:: insort(...)
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
63
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
64 Alias for :func:`insort_right`.
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
65
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
66
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
67 Examples
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
68 --------
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
69
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
70 .. _bisect-example:
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
71
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
72 The :func:`bisect` function is generally useful for categorizing numeric data.
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
73 This example uses :func:`bisect` to look up a letter grade for an exam total
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
74 (say) based on a set of ordered numeric breakpoints: 85 and up is an 'A', 75..84
46014
31cf38bdaac0 Enable doctest running for several other documents.
Georg Brandl <georg@python.org>
parents: 44383
diff changeset
75 is a 'B', etc.
42604
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
76
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
77 >>> grades = "FEDCBA"
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
78 >>> breakpoints = [30, 44, 66, 75, 85]
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
79 >>> from bisect import bisect
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
80 >>> def grade(total):
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
81 ... return grades[bisect(breakpoints, total)]
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
82 ...
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
83 >>> grade(66)
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
84 'C'
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
85 >>> map(grade, [33, 99, 77, 44, 12, 88])
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
86 ['E', 'A', 'B', 'D', 'F', 'A']
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
87
9e1529bf0442 Move the 3k reST doc tree in place.
Georg Brandl <georg@python.org>
parents:
diff changeset
88