This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

Title: Incorrect docs for bisect_left
Type: Stage:
Components: Documentation Versions: Python 3.6
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: rhettinger Nosy List: JackAidley, eloff, rhettinger, tim.peters
Priority: low Keywords:

Created on 2006-11-24 17:07 by eloff, last changed 2022-04-11 14:56 by admin. This issue is now closed.

Messages (6)
msg30663 - (view) Author: Daniel Eloff (eloff) Date: 2006-11-24 17:07
Return the index where to insert item x in list a, assuming a is sorted.
The return value i is such that all e in a[:i] have e < x, and all e in a[i:] have e >= x.  So if x already appears in the list, i points just before the leftmost x already there.

The last sentence is incorrect, and it contradicts what comes earlier. Not knowing which is correct, I had to test it in the shell.

>>> from bisect import *
>>> l = [1,2,3,3,3,4,5]
>>> bisect_left(l,3)
>>> l[2:]
[3, 3, 3, 4, 5]

It should be changed to read "i points at the leftmost x already there"

msg30664 - (view) Author: Tim Peters (tim.peters) * (Python committer) Date: 2006-11-24 19:16
The docs are written from the POV that indices in Python point /between/ array elements, which is the easiest way to understand slices, and that there are n+1 non-negative indices that "make obvious sense" in slices of a sequence with n elements:  index 0 points "just before" element a[0], and index n "just after" element a[n-1], while for 0 < i < n-1, index i points "just before" element [i] /and/ "just after" element a[i-1].

This is also the sanest way to understand the return value of the bisect functions, which again can return n+1 values given a sequence with n elements.

That said, I agree the docs are cryptic if you don't understand that first.  I'm not sure this is the best place to explain it.  The specific line in question could be "repaired" by saying a[i] is the leftmost x already there, identifying one of the n elements instead of one of the n+1 sequence positions.
msg30665 - (view) Author: Daniel Eloff (eloff) Date: 2006-12-03 22:39
That makes more sense, but if that's explained anywhere it was hidden away where I've never discovered it. I would be in favor of you're suggested fix to the line in question.

msg30666 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2007-04-03 00:02
Fixed.  See versions 54665 and 64666.
msg251955 - (view) Author: Jack Aidley (JackAidley) Date: 2015-09-30 17:21
This is still an issue in the latest version of the documentation.

It states "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."

But this is not true, the returned value DOES NOT meet these criteria.
msg251956 - (view) Author: Tim Peters (tim.peters) * (Python committer) Date: 2015-09-30 17:32
What's your objection?  Here's your original example:

>>> from bisect import *
>>> L = [1,2,3,3,3,4,5]
>>> x = 3
>>> i = bisect_left(L, x)
>>> i
>>> all(val < x for val in L[:i])
>>> all(val >= x for val in L[i:])

Which criteria are not met?
Date User Action Args
2022-04-11 14:56:21adminsetgithub: 44273
2015-09-30 17:32:21tim.peterssetmessages: + msg251956
2015-09-30 17:21:24JackAidleysetnosy: + JackAidley

messages: + msg251955
versions: + Python 3.6, - Python 2.5
2006-11-24 17:07:28eloffcreate