From 7c8626ab3db0b896052596066e1a2099b53ed135 Mon Sep 17 00:00:00 2001 From: Raymond Hettinger Date: Mon, 8 Aug 2022 23:31:50 -0700 Subject: Improvements to the bisect docs (GH-95807) --- Doc/library/bisect.rst | 38 +++++++++++++++++++------------------- 1 file 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. -- cgit v0.12