diff options
author | Raymond Hettinger <rhettinger@users.noreply.github.com> | 2022-08-09 06:31:50 (GMT) |
---|---|---|
committer | GitHub <noreply@github.com> | 2022-08-09 06:31:50 (GMT) |
commit | 7c8626ab3db0b896052596066e1a2099b53ed135 (patch) | |
tree | 4726cde090a1d38278bc212de964d79a08416b3f | |
parent | 8a55e2f9200288c353937cd5a0b83f0a3e282092 (diff) | |
download | cpython-7c8626ab3db0b896052596066e1a2099b53ed135.zip cpython-7c8626ab3db0b896052596066e1a2099b53ed135.tar.gz cpython-7c8626ab3db0b896052596066e1a2099b53ed135.tar.bz2 |
Improvements to the bisect docs (GH-95807)
-rw-r--r-- | Doc/library/bisect.rst | 38 |
1 files changed, 19 insertions, 19 deletions
diff --git a/Doc/library/bisect.rst b/Doc/library/bisect.rst index 513675d..76045ea 100644 --- a/Doc/library/bisect.rst +++ b/Doc/library/bisect.rst @@ -13,10 +13,16 @@ This module provides support for maintaining a list in sorted order without having to sort the list after each insertion. For long lists of items with -expensive comparison operations, this can be an improvement over the more common -approach. The module is called :mod:`bisect` because it uses a basic bisection -algorithm to do its work. The source code may be most useful as a working -example of the algorithm (the boundary conditions are already right!). +expensive comparison operations, this can be an improvement over +linear searches or frequent resorting. + +The module is called :mod:`bisect` because it uses a basic bisection +algorithm to do its work. Unlike other bisection tools that search for a +specific value, the functions in this module are designed to locate an +insertion point. Accordingly, the functions never call an :meth:`__eq__` +method to determine whether a value has been found. Instead, the +functions only call the :meth:`__lt__` method and will return an insertion +point between values in an array. The following functions are provided: @@ -30,16 +36,17 @@ The following functions are provided: any existing entries. The return value is suitable for use as the first 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. + The returned insertion point *ip* partitions the array *a* into two + slices such that ``all(elem < x for elem in a[lo : ip])`` is true for the + left slice and ``all(elem >= x for elem in a[ip : hi])`` is true for the + right slice. *key* specifies a :term:`key function` of one argument that is used to extract a comparison key from each element in the array. To support searching complex records, the key function is not applied to the *x* value. - If *key* is ``None``, the elements are compared directly with no - intervening function call. + If *key* is ``None``, the elements are compared directly and + no key function is called. .. versionchanged:: 3.10 Added the *key* parameter. @@ -51,16 +58,9 @@ The following functions are provided: 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. - - *key* specifies a :term:`key function` of one argument that is used to - extract a comparison key from each element in the array. To support - searching complex records, the key function is not applied to the *x* value. - - If *key* is ``None``, the elements are compared directly with no - intervening function call. + The returned insertion point *ip* partitions the array *a* into two slices + such that ``all(elem <= x for elem in a[lo : ip])`` is true for the left slice and + ``all(elem > x for elem in a[ip : hi])`` is true for the right slice. .. versionchanged:: 3.10 Added the *key* parameter. |