Documentation for bisect with keys

[SimpleArt]

Documentation

Missing documentation for keys in bisect functions' doc-strings.

I've also found the wording in the official documentation to be a little confusing. I think it might be clearer to use an overloaded definition like this:

bisect_left(a, x, lo=0, hi=None, *, key=None)
bisect_left(a, k, lo=0, hi=None, *, key)

Locate the insertion point for x in a to maintain sorted order. The parameters lo and hi may be used to
specify a subset of the list which should be considered; by default the entire list is used. If x is already
present in a, the insertion point will be before (to the left of) 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.

key specifies a key function of one argument that is used to extract a comparison key from each element in
the array. If given, k = key(x) should be given instead of x, which allows searching for an unknown x by known key.

If key is None, the elements are compared directly with no intervening function call.

Changed in version 3.10: Added the key parameter.

insort_left(a, x, lo=0, hi=None, *, key=None)

Insert x in a in sorted order.

This function first runs bisect_left() to locate an insertion point. Next, it runs the insert() method on a
to insert x at the appropriate position to maintain sort order.

To support inserting records in a table, the key function (if any) is applied to x for the search step but not for
the insertion step. Unlike bisect_left, key(x) should not be given in place of x since x needs to be inserted into a.

Keep in mind that the O(log n) search is dominated by the slow O(n) insertion step.

Changed in version 3.10: Added the key parameter.

Linked PRs

• GH-102833: Mention the key function in the docstrings #103009

[terryjreedy]

I don't know whether not adding key doc to docstrings was intentional or accidental. Given that docstrings are meant to be a condensed reminder of the full doc and how key changes the meaning of the second parameter, it might have been intentional.
@rhettinger ?

---

I agree that the current key doc is a bit confusing, but I dislike splitting the signature. I would like to suggest the following, which is true for the second parameter,

If given, x must be a key value that can be compared with the calculated keys.

as replacement for

If given, k = key(x) should be given instead of x, which allows searching for an unknown x by known key.

but everything above this sentence, I presume written before key functions were added, assumes that 'x' is an item similar to those in the list and a potential addition. I have more potential suggestions to fix this, but will hold them until Raymond replies.

For me, 'searching for an unknown x by known key' does not add anything.

[rhettinger]

Mostly, we keep the docstrings more terse than the main docs since they are mainly used as a reminder. Note, the min() and max() docstrings don't mention a key-function at all — it means the same everywhere it is used and is defined in the glossary.

That said, there is no downside to expanding the docstring a bit. So, I will add wording along the lines in the sorted() docstring: "A custom key function can be supplied to customize the sort order".

I think it might be clearer to use an overloaded definition like this

I don't think that is clearer at all.

FWIW, the wording that follows should add clarity and there are worked out examples at the bottom on the page. This should be all most people need.