[ python-Bugs-1602378 ] Incorrect docs for bisect_left

[SourceForge.net]

Bugs item #1602378, was opened at 2006-11-24 09:07
Message generated for change (Comment added) made by eloff
You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=105470&aid=1602378&group_id=5470

Please note that this message will contain a full copy of the comment thread,
including the initial issue submission, for this request,
not just the latest update.
Category: Documentation
Group: Python 2.5
Status: Open
Resolution: None
Priority: 5
Private: No
Submitted By: Daniel Eloff (eloff)
Assigned to: Raymond Hettinger (rhettinger)
Summary: Incorrect docs for bisect_left

Initial Comment:
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

----------------------------------------------------------------------

>Comment By: Daniel Eloff (eloff)
Date: 2006-12-03 14:39

Message:
Logged In: YES 
user_id=730918
Originator: YES

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

----------------------------------------------------------------------

Comment By: Tim Peters (tim_one)
Date: 2006-11-24 11:16

Message:
Logged In: YES 
user_id=31435
Originator: NO

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.

----------------------------------------------------------------------

You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=105470&aid=1602378&group_id=5470