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. <[email protected]>
7.. sectionauthor:: Raymond Hettinger <python at rcn.com>
8.. example based on the PyModules FAQ entry by Aaron Watters <[email protected]>
9
10**Source code:** :source:`Lib/bisect.py`
11
12--------------
13
14This module provides support for maintaining a list in sorted order without
15having to sort the list after each insertion.  For long lists of items with
16expensive comparison operations, this can be an improvement over the more common
17approach.  The module is called :mod:`bisect` because it uses a basic bisection
18algorithm to do its work.  The source code may be most useful as a working
19example of the algorithm (the boundary conditions are already right!).
20
21.. _bisect functions:
22
23The following functions are provided:
24
25
26.. function:: bisect_left(a, x, lo=0, hi=len(a), *, key=None)
27
28   Locate the insertion point for *x* in *a* to maintain sorted order.
29   The parameters *lo* and *hi* may be used to specify a subset of the list
30   which should be considered; by default the entire list is used.  If *x* is
31   already present in *a*, the insertion point will be before (to the left of)
32   any existing entries.  The return value is suitable for use as the first
33   parameter to ``list.insert()`` assuming that *a* is already sorted.
34
35   The returned insertion point *i* partitions the array *a* into two halves so
36   that ``all(val < x for val in a[lo : i])`` for the left side and
37   ``all(val >= x for val in a[i : hi])`` for the right side.
38
39   *key* specifies a :term:`key function` of one argument that is used to
40   extract a comparison key from each element in the array.  To support
41   searching complex records, the key function is not applied to the *x* value.
42
43   If *key* is ``None``, the elements are compared directly with no
44   intervening function call.
45
46   .. versionchanged:: 3.10
47      Added the *key* parameter.
48
49
50.. function:: bisect_right(a, x, lo=0, hi=len(a), *, key=None)
51              bisect(a, x, lo=0, hi=len(a), *, key=None)
52
53   Similar to :py:func:`~bisect.bisect_left`, but returns an insertion point which comes
54   after (to the right of) any existing entries of *x* in *a*.
55
56   The returned insertion point *i* partitions the array *a* into two halves so
57   that ``all(val <= x for val in a[lo : i])`` for the left side and
58   ``all(val > x for val in a[i : hi])`` for the right side.
59
60   *key* specifies a :term:`key function` of one argument that is used to
61   extract a comparison key from each element in the array.  To support
62   searching complex records, the key function is not applied to the *x* value.
63
64   If *key* is ``None``, the elements are compared directly with no
65   intervening function call.
66
67   .. versionchanged:: 3.10
68      Added the *key* parameter.
69
70
71.. function:: insort_left(a, x, lo=0, hi=len(a), *, key=None)
72
73   Insert *x* in *a* in sorted order.
74
75   This function first runs :py:func:`~bisect.bisect_left` to locate an insertion point.
76   Next, it runs the :meth:`insert` method on *a* to insert *x* at the
77   appropriate position to maintain sort order.
78
79   To support inserting records in a table, the *key* function (if any) is
80   applied to *x* for the search step but not for the insertion step.
81
82   Keep in mind that the ``O(log n)`` search is dominated by the slow O(n)
83   insertion step.
84
85   .. versionchanged:: 3.10
86      Added the *key* parameter.
87
88
89.. function:: insort_right(a, x, lo=0, hi=len(a), *, key=None)
90              insort(a, x, lo=0, hi=len(a), *, key=None)
91
92   Similar to :py:func:`~bisect.insort_left`, but inserting *x* in *a* after any existing
93   entries of *x*.
94
95   This function first runs :py:func:`~bisect.bisect_right` to locate an insertion point.
96   Next, it runs the :meth:`insert` method on *a* to insert *x* at the
97   appropriate position to maintain sort order.
98
99   To support inserting records in a table, the *key* function (if any) is
100   applied to *x* for the search step but not for the insertion step.
101
102   Keep in mind that the ``O(log n)`` search is dominated by the slow O(n)
103   insertion step.
104
105   .. versionchanged:: 3.10
106      Added the *key* parameter.
107
108
109Performance Notes
110-----------------
111
112When writing time sensitive code using *bisect()* and *insort()*, keep these
113thoughts in mind:
114
115* Bisection is effective for searching ranges of values.
116  For locating specific values, dictionaries are more performant.
117
118* The *insort()* functions are ``O(n)`` because the logarithmic search step
119  is dominated by the linear time insertion step.
120
121* The search functions are stateless and discard key function results after
122  they are used.  Consequently, if the search functions are used in a loop,
123  the key function may be called again and again on the same array elements.
124  If the key function isn't fast, consider wrapping it with
125  :py:func:`functools.cache` to avoid duplicate computations.  Alternatively,
126  consider searching an array of precomputed keys to locate the insertion
127  point (as shown in the examples section below).
128
129.. seealso::
130
131   * `Sorted Collections
132     <https://grantjenks.com/docs/sortedcollections/>`_ is a high performance
133     module that uses *bisect* to managed sorted collections of data.
134
135   * The `SortedCollection recipe
136     <https://code.activestate.com/recipes/577197-sortedcollection/>`_ uses
137     bisect to build a full-featured collection class with straight-forward search
138     methods and support for a key-function.  The keys are precomputed to save
139     unnecessary calls to the key function during searches.
140
141
142Searching Sorted Lists
143----------------------
144
145The above `bisect functions`_ are useful for finding insertion points but
146can be tricky or awkward to use for common searching tasks. The following five
147functions show how to transform them into the standard lookups for sorted
148lists::
149
150    def index(a, x):
151        'Locate the leftmost value exactly equal to x'
152        i = bisect_left(a, x)
153        if i != len(a) and a[i] == x:
154            return i
155        raise ValueError
156
157    def find_lt(a, x):
158        'Find rightmost value less than x'
159        i = bisect_left(a, x)
160        if i:
161            return a[i-1]
162        raise ValueError
163
164    def find_le(a, x):
165        'Find rightmost value less than or equal to x'
166        i = bisect_right(a, x)
167        if i:
168            return a[i-1]
169        raise ValueError
170
171    def find_gt(a, x):
172        'Find leftmost value greater than x'
173        i = bisect_right(a, x)
174        if i != len(a):
175            return a[i]
176        raise ValueError
177
178    def find_ge(a, x):
179        'Find leftmost item greater than or equal to x'
180        i = bisect_left(a, x)
181        if i != len(a):
182            return a[i]
183        raise ValueError
184
185
186Examples
187--------
188
189.. _bisect-example:
190
191The :py:func:`~bisect.bisect` function can be useful for numeric table lookups. This
192example uses :py:func:`~bisect.bisect` to look up a letter grade for an exam score (say)
193based on a set of ordered numeric breakpoints: 90 and up is an 'A', 80 to 89 is
194a 'B', and so on::
195
196   >>> def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):
197   ...     i = bisect(breakpoints, score)
198   ...     return grades[i]
199   ...
200   >>> [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]
201   ['F', 'A', 'C', 'C', 'B', 'A', 'A']
202
203The :py:func:`~bisect.bisect` and :py:func:`~bisect.insort` functions also work with
204lists of tuples.  The *key* argument can serve to extract the field used for ordering
205records in a table::
206
207    >>> from collections import namedtuple
208    >>> from operator import attrgetter
209    >>> from bisect import bisect, insort
210    >>> from pprint import pprint
211
212    >>> Movie = namedtuple('Movie', ('name', 'released', 'director'))
213
214    >>> movies = [
215    ...     Movie('Jaws', 1975, 'Spielberg'),
216    ...     Movie('Titanic', 1997, 'Cameron'),
217    ...     Movie('The Birds', 1963, 'Hitchcock'),
218    ...     Movie('Aliens', 1986, 'Cameron')
219    ... ]
220
221    >>> # Find the first movie released after 1960
222    >>> by_year = attrgetter('released')
223    >>> movies.sort(key=by_year)
224    >>> movies[bisect(movies, 1960, key=by_year)]
225    Movie(name='The Birds', released=1963, director='Hitchcock')
226
227    >>> # Insert a movie while maintaining sort order
228    >>> romance = Movie('Love Story', 1970, 'Hiller')
229    >>> insort(movies, romance, key=by_year)
230    >>> pprint(movies)
231    [Movie(name='The Birds', released=1963, director='Hitchcock'),
232     Movie(name='Love Story', released=1970, director='Hiller'),
233     Movie(name='Jaws', released=1975, director='Spielberg'),
234     Movie(name='Aliens', released=1986, director='Cameron'),
235     Movie(name='Titanic', released=1997, director='Cameron')]
236
237If the key function is expensive, it is possible to avoid repeated function
238calls by searching a list of precomputed keys to find the index of a record::
239
240    >>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
241    >>> data.sort(key=lambda r: r[1])       # Or use operator.itemgetter(1).
242    >>> keys = [r[1] for r in data]         # Precompute a list of keys.
243    >>> data[bisect_left(keys, 0)]
244    ('black', 0)
245    >>> data[bisect_left(keys, 1)]
246    ('blue', 1)
247    >>> data[bisect_left(keys, 5)]
248    ('red', 5)
249    >>> data[bisect_left(keys, 8)]
250    ('yellow', 8)
251