Incorrect docs for bisect_left

[eloff]

BPO	1602378
Nosy	@tim-one, @rhettinger

^{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:

assignee = 'https://github.com/rhettinger'
closed_at = <Date 2015-09-30.17:32:21.515>
created_at = <Date 2006-11-24.17:07:28.000>
labels = ['docs']
title = 'Incorrect docs for bisect_left'
updated_at = <Date 2015-09-30.17:32:21.515>
user = 'https://bugs.python.org/eloff'

bugs.python.org fields:

activity = <Date 2015-09-30.17:32:21.515>
actor = 'tim.peters'
assignee = 'rhettinger'
closed = True
closed_date = None
closer = None
components = ['Documentation']
creation = <Date 2006-11-24.17:07:28.000>
creator = 'eloff'
dependencies = []
files = []
hgrepos = []
issue_num = 1602378
keywords = []
message_count = 6.0
messages = ['30663', '30664', '30665', '30666', '251955', '251956']
nosy_count = 4.0
nosy_names = ['tim.peters', 'rhettinger', 'eloff', 'JackAidley']
pr_nums = []
priority = 'low'
resolution = 'fixed'
stage = None
status = 'closed'
superseder = None
type = None
url = 'https://bugs.python.org/issue1602378'
versions = ['Python 3.6']

[eloff]

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

[tim-one]

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.

[eloff]

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

[rhettinger]

Fixed. See versions 54665 and 64666.

[JackAidley]

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.

[tim-one]

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?