New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Incorrect docs for bisect_left #44273
Comments
Quote: 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)
2
>>> l[2:]
[3, 3, 3, 4, 5] It should be changed to read "i points at the leftmost x already there" -Dan |
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. |
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. -Dan |
Fixed. See versions 54665 and 64666. |
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. |
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
2
>>> all(val < x for val in L[:i])
True
>>> all(val >= x for val in L[i:])
True Which criteria are not met? |
Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.
Show more details
GitHub fields:
bugs.python.org fields:
The text was updated successfully, but these errors were encountered: