[Python-checkins] r84385 - python/branches/release31-maint/Doc/library/bisect.rst
raymond.hettinger
python-checkins at python.org
Wed Sep 1 10:24:40 CEST 2010
Author: raymond.hettinger
Date: Wed Sep 1 10:24:40 2010
New Revision: 84385
Log:
Clean-up bisect docs
Modified:
python/branches/release31-maint/Doc/library/bisect.rst
Modified: python/branches/release31-maint/Doc/library/bisect.rst
==============================================================================
--- python/branches/release31-maint/Doc/library/bisect.rst (original)
+++ python/branches/release31-maint/Doc/library/bisect.rst Wed Sep 1 10:24:40 2010
@@ -4,6 +4,7 @@
.. module:: bisect
:synopsis: Array bisection algorithms for binary searching.
.. sectionauthor:: Fred L. Drake, Jr. <fdrake at acm.org>
+.. sectionauthor:: Raymond Hettinger <python at rcn.com>
.. example based on the PyModules FAQ entry by Aaron Watters <arw at pythonpros.com>
This module provides support for maintaining a list in sorted order without
@@ -18,13 +19,16 @@
.. function:: bisect_left(a, x, lo=0, hi=len(a))
- Locate the proper insertion point for *x* in *a* to maintain sorted order.
+ 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()``. This assumes that *a* is already sorted.
+ parameter to ``list.insert()`` assuming that *a* is already sorted.
+ 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))
@@ -32,16 +36,16 @@
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)``. This assumes that *a* is
- already sorted.
-
- Also note that while the fast search step is O(log n), the slower insertion
- step is O(n), so the overall operation is slow.
-
+ ``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))
@@ -49,71 +53,75 @@
Similar to :func:`insort_left`, but inserting *x* in *a* after any existing
entries of *x*.
- Also note that while the fast search step is O(log n), the slower insertion
- step is O(n), so the overall operation is slow.
+.. 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.
+
Searching Sorted Lists
----------------------
-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 three
+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::
- def find(a, key):
- '''Find leftmost item exact equal to the key.
- Raise ValueError if no such item exists.
-
- '''
- i = bisect_left(a, key)
- if i < len(a) and a[i] == key:
+ 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('No item found with key equal to: %r' % (key,))
+ raise ValueError
- def find_le(a, key):
- '''Find largest item less-than or equal to key.
- Raise ValueError if no such item exists.
- If multiple keys are equal, return the leftmost.
-
- '''
- i = bisect_left(a, key)
- if i < len(a) and a[i] == key:
+ 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]
- if i == 0:
- raise ValueError('No item found with key at or below: %r' % (key,))
- return a[i-1]
-
- def find_ge(a, key):
- '''Find smallest item greater-than or equal to key.
- Raise ValueError if no such item exists.
- If multiple keys are equal, return the leftmost.
-
- '''
- i = bisect_left(a, key)
- if i == len(a):
- raise ValueError('No item found with key at or above: %r' % (key,))
- return a[i]
+ raise ValueError
+
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.
-
- >>> grades = "FEDCBA"
- >>> breakpoints = [30, 44, 66, 75, 85]
- >>> from bisect import bisect
- >>> def grade(total):
- ... return grades[bisect(breakpoints, total)]
+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::
+
+ >>> def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):
+ ... i = bisect(breakpoints, score)
+ ... return grades[i]
...
- >>> grade(66)
- 'C'
- >>> map(grade, [33, 99, 77, 44, 12, 88])
- ['E', 'A', 'B', 'D', 'F', 'A']
+ >>> [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
@@ -135,9 +143,3 @@
>>> data[bisect_left(keys, 8)]
('yellow', 8)
-.. seealso::
-
- `SortedCollection recipe
- <http://code.activestate.com/recipes/577197-sortedcollection/>`_ that
- encapsulates precomputed keys, allowing straight-forward insertion and
- searching using a *key* function.
More information about the Python-checkins
mailing list