Georg Brandl | 116aa62 | 2007-08-15 14:28:22 +0000 | [diff] [blame] | 1 | :mod:`bisect` --- Array bisection algorithm |
| 2 | =========================================== |
| 3 | |
| 4 | .. module:: bisect |
| 5 | :synopsis: Array bisection algorithms for binary searching. |
| 6 | .. sectionauthor:: Fred L. Drake, Jr. <fdrake@acm.org> |
Raymond Hettinger | 20933e0 | 2010-09-01 06:58:25 +0000 | [diff] [blame] | 7 | .. sectionauthor:: Raymond Hettinger <python at rcn.com> |
Christian Heimes | 5b5e81c | 2007-12-31 16:14:33 +0000 | [diff] [blame] | 8 | .. example based on the PyModules FAQ entry by Aaron Watters <arw@pythonpros.com> |
Georg Brandl | 116aa62 | 2007-08-15 14:28:22 +0000 | [diff] [blame] | 9 | |
Raymond Hettinger | 1048094 | 2011-01-10 03:26:08 +0000 | [diff] [blame] | 10 | **Source code:** :source:`Lib/bisect.py` |
| 11 | |
Georg Brandl | 116aa62 | 2007-08-15 14:28:22 +0000 | [diff] [blame] | 12 | This module provides support for maintaining a list in sorted order without |
| 13 | having to sort the list after each insertion. For long lists of items with |
| 14 | expensive comparison operations, this can be an improvement over the more common |
| 15 | approach. The module is called :mod:`bisect` because it uses a basic bisection |
| 16 | algorithm to do its work. The source code may be most useful as a working |
| 17 | example of the algorithm (the boundary conditions are already right!). |
| 18 | |
| 19 | The following functions are provided: |
| 20 | |
| 21 | |
Georg Brandl | 0d8f073 | 2009-04-05 22:20:44 +0000 | [diff] [blame] | 22 | .. function:: bisect_left(a, x, lo=0, hi=len(a)) |
Georg Brandl | 116aa62 | 2007-08-15 14:28:22 +0000 | [diff] [blame] | 23 | |
Raymond Hettinger | 20933e0 | 2010-09-01 06:58:25 +0000 | [diff] [blame] | 24 | Locate the insertion point for *x* in *a* to maintain sorted order. |
Georg Brandl | 0d8f073 | 2009-04-05 22:20:44 +0000 | [diff] [blame] | 25 | The parameters *lo* and *hi* may be used to specify a subset of the list |
| 26 | which should be considered; by default the entire list is used. If *x* is |
| 27 | already present in *a*, the insertion point will be before (to the left of) |
| 28 | any existing entries. The return value is suitable for use as the first |
Raymond Hettinger | 20933e0 | 2010-09-01 06:58:25 +0000 | [diff] [blame] | 29 | parameter to ``list.insert()`` assuming that *a* is already sorted. |
Georg Brandl | 116aa62 | 2007-08-15 14:28:22 +0000 | [diff] [blame] | 30 | |
Raymond Hettinger | 20933e0 | 2010-09-01 06:58:25 +0000 | [diff] [blame] | 31 | The returned insertion point *i* partitions the array *a* into two halves so |
| 32 | that ``all(val < x for val in a[lo:i])`` for the left side and |
| 33 | ``all(val >= x for val in a[i:hi])`` for the right side. |
Georg Brandl | 116aa62 | 2007-08-15 14:28:22 +0000 | [diff] [blame] | 34 | |
Georg Brandl | 0d8f073 | 2009-04-05 22:20:44 +0000 | [diff] [blame] | 35 | .. function:: bisect_right(a, x, lo=0, hi=len(a)) |
| 36 | bisect(a, x, lo=0, hi=len(a)) |
Georg Brandl | 116aa62 | 2007-08-15 14:28:22 +0000 | [diff] [blame] | 37 | |
Georg Brandl | 0d8f073 | 2009-04-05 22:20:44 +0000 | [diff] [blame] | 38 | Similar to :func:`bisect_left`, but returns an insertion point which comes |
| 39 | after (to the right of) any existing entries of *x* in *a*. |
Georg Brandl | 116aa62 | 2007-08-15 14:28:22 +0000 | [diff] [blame] | 40 | |
Raymond Hettinger | 20933e0 | 2010-09-01 06:58:25 +0000 | [diff] [blame] | 41 | The returned insertion point *i* partitions the array *a* into two halves so |
| 42 | that ``all(val <= x for val in a[lo:i])`` for the left side and |
| 43 | ``all(val > x for val in a[i:hi])`` for the right side. |
Georg Brandl | 116aa62 | 2007-08-15 14:28:22 +0000 | [diff] [blame] | 44 | |
Georg Brandl | 0d8f073 | 2009-04-05 22:20:44 +0000 | [diff] [blame] | 45 | .. function:: insort_left(a, x, lo=0, hi=len(a)) |
Georg Brandl | 116aa62 | 2007-08-15 14:28:22 +0000 | [diff] [blame] | 46 | |
Georg Brandl | 0d8f073 | 2009-04-05 22:20:44 +0000 | [diff] [blame] | 47 | Insert *x* in *a* in sorted order. This is equivalent to |
Raymond Hettinger | 20933e0 | 2010-09-01 06:58:25 +0000 | [diff] [blame] | 48 | ``a.insert(bisect.bisect_left(a, x, lo, hi), x)`` assuming that *a* is |
| 49 | already sorted. Keep in mind that the O(log n) search is dominated by |
| 50 | the slow O(n) insertion step. |
Georg Brandl | 116aa62 | 2007-08-15 14:28:22 +0000 | [diff] [blame] | 51 | |
Georg Brandl | 0d8f073 | 2009-04-05 22:20:44 +0000 | [diff] [blame] | 52 | .. function:: insort_right(a, x, lo=0, hi=len(a)) |
| 53 | insort(a, x, lo=0, hi=len(a)) |
Georg Brandl | 116aa62 | 2007-08-15 14:28:22 +0000 | [diff] [blame] | 54 | |
Georg Brandl | 0d8f073 | 2009-04-05 22:20:44 +0000 | [diff] [blame] | 55 | Similar to :func:`insort_left`, but inserting *x* in *a* after any existing |
| 56 | entries of *x*. |
Georg Brandl | 116aa62 | 2007-08-15 14:28:22 +0000 | [diff] [blame] | 57 | |
Raymond Hettinger | 20933e0 | 2010-09-01 06:58:25 +0000 | [diff] [blame] | 58 | .. seealso:: |
| 59 | |
| 60 | `SortedCollection recipe |
| 61 | <http://code.activestate.com/recipes/577197-sortedcollection/>`_ that uses |
| 62 | bisect to build a full-featured collection class with straight-forward search |
| 63 | methods and support for a key-function. The keys are precomputed to save |
| 64 | unnecessary calls to the key function during searches. |
| 65 | |
Georg Brandl | 116aa62 | 2007-08-15 14:28:22 +0000 | [diff] [blame] | 66 | |
Raymond Hettinger | 87c9d6c | 2010-08-07 07:36:55 +0000 | [diff] [blame] | 67 | Searching Sorted Lists |
| 68 | ---------------------- |
| 69 | |
Raymond Hettinger | 20933e0 | 2010-09-01 06:58:25 +0000 | [diff] [blame] | 70 | The above :func:`bisect` functions are useful for finding insertion points but |
| 71 | can be tricky or awkward to use for common searching tasks. The following five |
Raymond Hettinger | 87c9d6c | 2010-08-07 07:36:55 +0000 | [diff] [blame] | 72 | functions show how to transform them into the standard lookups for sorted |
| 73 | lists:: |
| 74 | |
Raymond Hettinger | 20933e0 | 2010-09-01 06:58:25 +0000 | [diff] [blame] | 75 | def index(a, x): |
| 76 | 'Locate the leftmost value exactly equal to x' |
| 77 | i = bisect_left(a, x) |
| 78 | if i != len(a) and a[i] == x: |
| 79 | return i |
| 80 | raise ValueError |
Raymond Hettinger | 87c9d6c | 2010-08-07 07:36:55 +0000 | [diff] [blame] | 81 | |
Raymond Hettinger | 20933e0 | 2010-09-01 06:58:25 +0000 | [diff] [blame] | 82 | def find_lt(a, x): |
| 83 | 'Find rightmost value less than x' |
| 84 | i = bisect_left(a, x) |
| 85 | if i: |
| 86 | return a[i-1] |
| 87 | raise ValueError |
| 88 | |
| 89 | def find_le(a, x): |
| 90 | 'Find rightmost value less than or equal to x' |
| 91 | i = bisect_right(a, x) |
| 92 | if i: |
| 93 | return a[i-1] |
| 94 | raise ValueError |
| 95 | |
| 96 | def find_gt(a, x): |
| 97 | 'Find leftmost value greater than x' |
| 98 | i = bisect_right(a, x) |
| 99 | if i != len(a): |
Raymond Hettinger | 87c9d6c | 2010-08-07 07:36:55 +0000 | [diff] [blame] | 100 | return a[i] |
Raymond Hettinger | 20933e0 | 2010-09-01 06:58:25 +0000 | [diff] [blame] | 101 | raise ValueError |
Raymond Hettinger | 87c9d6c | 2010-08-07 07:36:55 +0000 | [diff] [blame] | 102 | |
Raymond Hettinger | 20933e0 | 2010-09-01 06:58:25 +0000 | [diff] [blame] | 103 | def find_ge(a, x): |
| 104 | 'Find leftmost item greater than or equal to x' |
| 105 | i = bisect_left(a, x) |
| 106 | if i != len(a): |
Raymond Hettinger | 87c9d6c | 2010-08-07 07:36:55 +0000 | [diff] [blame] | 107 | return a[i] |
Raymond Hettinger | 20933e0 | 2010-09-01 06:58:25 +0000 | [diff] [blame] | 108 | raise ValueError |
Raymond Hettinger | 87c9d6c | 2010-08-07 07:36:55 +0000 | [diff] [blame] | 109 | |
Raymond Hettinger | 87c9d6c | 2010-08-07 07:36:55 +0000 | [diff] [blame] | 110 | |
| 111 | Other Examples |
| 112 | -------------- |
Georg Brandl | 116aa62 | 2007-08-15 14:28:22 +0000 | [diff] [blame] | 113 | |
| 114 | .. _bisect-example: |
| 115 | |
Raymond Hettinger | 20933e0 | 2010-09-01 06:58:25 +0000 | [diff] [blame] | 116 | The :func:`bisect` function can be useful for numeric table lookups. This |
| 117 | example uses :func:`bisect` to look up a letter grade for an exam score (say) |
| 118 | based on a set of ordered numeric breakpoints: 90 and up is an 'A', 80 to 89 is |
| 119 | a 'B', and so on:: |
Georg Brandl | 116aa62 | 2007-08-15 14:28:22 +0000 | [diff] [blame] | 120 | |
Raymond Hettinger | 20933e0 | 2010-09-01 06:58:25 +0000 | [diff] [blame] | 121 | >>> def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'): |
| 122 | ... i = bisect(breakpoints, score) |
| 123 | ... return grades[i] |
Georg Brandl | 116aa62 | 2007-08-15 14:28:22 +0000 | [diff] [blame] | 124 | ... |
Raymond Hettinger | 20933e0 | 2010-09-01 06:58:25 +0000 | [diff] [blame] | 125 | >>> [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]] |
| 126 | ['F', 'A', 'C', 'C', 'B', 'A', 'A'] |
Georg Brandl | 116aa62 | 2007-08-15 14:28:22 +0000 | [diff] [blame] | 127 | |
Raymond Hettinger | e046d2a | 2009-06-11 22:01:24 +0000 | [diff] [blame] | 128 | Unlike the :func:`sorted` function, it does not make sense for the :func:`bisect` |
| 129 | functions to have *key* or *reversed* arguments because that would lead to an |
Georg Brandl | 6faee4e | 2010-09-21 14:48:28 +0000 | [diff] [blame] | 130 | inefficient design (successive calls to bisect functions would not "remember" |
Raymond Hettinger | e046d2a | 2009-06-11 22:01:24 +0000 | [diff] [blame] | 131 | all of the previous key lookups). |
Georg Brandl | 116aa62 | 2007-08-15 14:28:22 +0000 | [diff] [blame] | 132 | |
Raymond Hettinger | e046d2a | 2009-06-11 22:01:24 +0000 | [diff] [blame] | 133 | Instead, it is better to search a list of precomputed keys to find the index |
| 134 | of the record in question:: |
| 135 | |
| 136 | >>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)] |
Raymond Hettinger | 27352a5 | 2009-06-11 22:06:06 +0000 | [diff] [blame] | 137 | >>> data.sort(key=lambda r: r[1]) |
| 138 | >>> keys = [r[1] for r in data] # precomputed list of keys |
Raymond Hettinger | e046d2a | 2009-06-11 22:01:24 +0000 | [diff] [blame] | 139 | >>> data[bisect_left(keys, 0)] |
| 140 | ('black', 0) |
| 141 | >>> data[bisect_left(keys, 1)] |
| 142 | ('blue', 1) |
| 143 | >>> data[bisect_left(keys, 5)] |
| 144 | ('red', 5) |
| 145 | >>> data[bisect_left(keys, 8)] |
| 146 | ('yellow', 8) |
Raymond Hettinger | 87c9d6c | 2010-08-07 07:36:55 +0000 | [diff] [blame] | 147 | |