CODEWITHSUNDEEP
python-3.xsorting
HeadzzZ
HeadzzZ

Reputation: 99

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

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?

Upvotes: 0

Views: 341

Answers (1)

MisterMiyagi
MisterMiyagi

Reputation: 50106

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.

Upvotes: 1

Related Questions