| msg30663 - (view) |
Author: Daniel Eloff (eloff) |
Date: 2006-11-24 17:07 |
| Quote: 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) 2 >>> l[2:] [3, 3, 3, 4, 5] It should be changed to read "i points at the leftmost x already there" -Dan |
|
|
| msg30664 - (view) |
Author: Tim Peters (tim.peters) *  |
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. -Dan |
|
|
| msg30666 - (view) |
Author: Raymond Hettinger (rhettinger) * |
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) * |
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 2 >>> all(val < x for val in L[:i]) True >>> all(val >= x for val in L[i:]) True Which criteria are not met? |
|
|