[FIXED] Python3 bisect_left: return value does not match the Python documentation description

Issue

My codes are as follows:

import bisect
a = [186, 186, 150, 200, 160, 130, 197, 200]
print("left",bisect.bisect_left(a,150))

The return value is: 0

But as specified in the document of Python 3.9:

If x is already present in a, the insertion point will be before (to the left of) any existing entries.

150 exists in the list "a", so the return value should be 1 (i.e., a.index(150) - 1), but the actual returned value is 0 . Would you please explain the reason?

Solution

The bisect module and generally the underlying binary search algorithm is made for sorted data. For unsorted data, the result is effectively arbitrary.

For the bisect_left algorithm sorted-ness means the algorithm does not have to check for equality: In a sequence a the position i "to the left" of any existing x is the one where a[i] < x and x <= a[i + 1]. This is because sorted-ness enforces a[j] <= a[j+1].
As such, technically the insertion point will be before (to the left of) any existing entries equal or larger than x. Sorted-ness guarantees that this is before any existing entries of x.

For the sequence [186, 186, 150, 200, 160, 130, 197, 200] and x=150, the insertion point is 0 because:

• The list is initially bisected into [186, 186, 150, 200] and [160, ...].
• The head of the right bisect is equal or larger than x; assuming sorted'ness, there cannot be a value smaller than x in it.
• All values in the left bisect are equal or larger than x; assuming sorted'ness, the insertion point must be before all of them.

The only point before all values of the left bisection is 0.

Answered By - MisterMiyagi