From 87c9d6cf9cbf2cada6a309cf4e46d77c3484b4c2 Mon Sep 17 00:00:00 2001 From: Raymond Hettinger Date: Sat, 7 Aug 2010 07:36:55 +0000 Subject: Improve the docs for bisect to cover common searching tasks. --- Doc/library/bisect.rst | 60 +++++++++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 57 insertions(+), 3 deletions(-) diff --git a/Doc/library/bisect.rst b/Doc/library/bisect.rst index 3890d68..bcbcb07 100644 --- a/Doc/library/bisect.rst +++ b/Doc/library/bisect.rst @@ -39,6 +39,9 @@ The following functions are provided: ``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. + .. function:: insort_right(a, x, lo=0, hi=len(a)) insort(a, x, lo=0, hi=len(a)) @@ -46,9 +49,53 @@ The following functions are provided: Similar to :func:`insort_left`, but inserting *x* in *a* after any existing entries of *x*. - -Examples --------- + 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. + +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 +functions show how to transform them into the standard lookups for sorted +lists:: + + def find(a, key): + '''Find item with a key-value equal to key. + Raise ValueError if no such item exists. + + ''' + i = bisect_left(a, key) + if i < len(a) and a[i] == key: + return a[i] + raise ValueError('No item found with key equal to: %r' % (key,)) + + def find_le(a, key): + '''Find largest item with a key-value less-than or equal to key. + Raise ValueError if no such item exists. + If multiple key-values are equal, return the leftmost. + + ''' + i = bisect_left(a, key) + if i < len(a) and a[i] == key: + 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 with a key-value greater-than or equal to key. + Raise ValueError if no such item exists. + If multiple key-values 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] + +Other Examples +-------------- .. _bisect-example: @@ -87,3 +134,10 @@ of the record in question:: ('red', 5) >>> data[bisect_left(keys, 8)] ('yellow', 8) + +.. seealso:: + + `SortedCollection recipe + `_ that + encapsulates precomputed keys, allowing straight-forward insertion and + searching using a *key* function. -- cgit v0.12