Changeset 391 for python/trunk/Doc/library/bisect.rst

Timestamp:

Mar 19, 2014, 11:31:01 PM (11 years ago)

Author:

dmik

Message:

python: Merge vendor 2.7.6 to trunk.

Location:

python/trunk

Files:

• . (modified) (1 prop)
• Doc/library/bisect.rst (modified) (4 diffs)

python/trunk/Doc/library/bisect.rst

@@ -1 @@
-
 :mod:`bisect` --- Array bisection algorithm
 ===========================================
@@ -6 +5 @@
    :synopsis: Array bisection algorithms for binary searching.
 .. sectionauthor:: Fred L. Drake, Jr. <fdrake@acm.org>
+.. sectionauthor:: Raymond Hettinger <python at rcn.com>
 .. example based on the PyModules FAQ entry by Aaron Watters <arw@pythonpros.com>
+
+.. versionadded:: 2.1
+
+**Source code:** :source:`Lib/bisect.py`
+
+--------------
 
 This module provides support for maintaining a list in sorted order without
@@ -18 +24 @@
 
 
-.. function:: bisect_left(list, item[, lo[, hi]])
+.. function:: bisect_left(a, x, lo=0, hi=len(a))
 
-   Locate the proper insertion point for *item* in *list* to maintain sorted order.
-   The parameters *lo* and *hi* may be used to specify a subset of the list which
-   should be considered; by default the entire list is used.  If *item* is already
-   present in *list*, the insertion point will be before (to the left of) any
-   existing entries.  The return value is suitable for use as the first parameter
-   to ``list.insert()``.  This assumes that *list* is already sorted.
+   Locate the insertion point for *x* in *a* to maintain sorted order.
+   The parameters *lo* and *hi* may be used to specify a subset of the list
+   which should be considered; by default the entire list is used.  If *x* is
+   already present in *a*, the insertion point will be before (to the left of)
+   any existing entries.  The return value is suitable for use as the first
+   parameter to ``list.insert()`` assuming that *a* is already sorted.
 
-   .. versionadded:: 2.1
+   The returned insertion point *i* partitions the array *a* into two halves so
+   that ``all(val < x for val in a[lo:i])`` for the left side and
+   ``all(val >= x for val in a[i:hi])`` for the right side.
+
+.. function:: bisect_right(a, x, lo=0, hi=len(a))
+              bisect(a, x, lo=0, hi=len(a))
+
+   Similar to :func:`bisect_left`, but returns an insertion point which comes
+   after (to the right of) any existing entries of *x* in *a*.
+
+   The returned insertion point *i* partitions the array *a* into two halves so
+   that ``all(val <= x for val in a[lo:i])`` for the left side and
+   ``all(val > x for val in a[i:hi])`` for the right side.
+
+.. function:: insort_left(a, x, lo=0, hi=len(a))
+
+   Insert *x* in *a* in sorted order.  This is equivalent to
+   ``a.insert(bisect.bisect_left(a, x, lo, hi), x)`` assuming that *a* is
+   already sorted.  Keep in mind that the O(log n) search is dominated by
+   the slow O(n) insertion step.
+
+.. function:: insort_right(a, x, lo=0, hi=len(a))
+              insort(a, x, lo=0, hi=len(a))
+
+   Similar to :func:`insort_left`, but inserting *x* in *a* after any existing
+   entries of *x*.
+
+.. seealso::
+
+   `SortedCollection recipe
+   <http://code.activestate.com/recipes/577197-sortedcollection/>`_ that uses
+   bisect to build a full-featured collection class with straight-forward search
+   methods and support for a key-function.  The keys are precomputed to save
+   unnecessary calls to the key function during searches.
 
 
-.. function:: bisect_right(list, item[, lo[, hi]])
+Searching Sorted Lists
+----------------------
 
-   Similar to :func:`bisect_left`, but returns an insertion point which comes after
-   (to the right of) any existing entries of *item* in *list*.
+The above :func:`bisect` functions are useful for finding insertion points but
+can be tricky or awkward to use for common searching tasks. The following five
+functions show how to transform them into the standard lookups for sorted
+lists::
 
-   .. versionadded:: 2.1
+    def index(a, x):
+        'Locate the leftmost value exactly equal to x'
+        i = bisect_left(a, x)
+        if i != len(a) and a[i] == x:
+            return i
+        raise ValueError
+
+    def find_lt(a, x):
+        'Find rightmost value less than x'
+        i = bisect_left(a, x)
+        if i:
+            return a[i-1]
+        raise ValueError
+
+    def find_le(a, x):
+        'Find rightmost value less than or equal to x'
+        i = bisect_right(a, x)
+        if i:
+            return a[i-1]
+        raise ValueError
+
+    def find_gt(a, x):
+        'Find leftmost value greater than x'
+        i = bisect_right(a, x)
+        if i != len(a):
+            return a[i]
+        raise ValueError
+
+    def find_ge(a, x):
+        'Find leftmost item greater than or equal to x'
+        i = bisect_left(a, x)
+        if i != len(a):
+            return a[i]
+        raise ValueError
 
 
-.. function:: bisect(...)
-
-   Alias for :func:`bisect_right`.
-
-
-.. function:: insort_left(list, item[, lo[, hi]])
-
-   Insert *item* in *list* in sorted order.  This is equivalent to
-   ``list.insert(bisect.bisect_left(list, item, lo, hi), item)``.  This assumes
-   that *list* is already sorted.
-
-   .. versionadded:: 2.1
-
-
-.. function:: insort_right(list, item[, lo[, hi]])
-
-   Similar to :func:`insort_left`, but inserting *item* in *list* after any
-   existing entries of *item*.
-
-   .. versionadded:: 2.1
-
-
-.. function:: insort(...)
-
-   Alias for :func:`insort_right`.
-
-
-Examples
---------
+Other Examples
+--------------
 
 .. _bisect-example:
 
-The :func:`bisect` function is generally useful for categorizing numeric data.
-This example uses :func:`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.
+The :func:`bisect` function can be useful for numeric table lookups. This
+example uses :func:`bisect` to look up a letter grade for an exam score (say)
+based on a set of ordered numeric breakpoints: 90 and up is an 'A', 80 to 89 is
+a 'B', and so on::
 
-   >>> 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']
+   >>> def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):
+           i = bisect(breakpoints, score)
+           return grades[i]
+
+   >>> [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]
+   ['F', 'A', 'C', 'C', 'B', 'A', 'A']
 
 Unlike the :func:`sorted` function, it does not make sense for the :func:`bisect`
 functions to have *key* or *reversed* arguments because that would lead to an
-inefficent design (successive calls to bisect functions would not "remember"
+inefficient design (successive calls to bisect functions would not "remember"
 all of the previous key lookups).
 
@@ -105 +149 @@
     >>> data[bisect_left(keys, 8)]
     ('yellow', 8)
+