CODEWITHSUNDEEP
pythonpython-3.8
coderhk
coderhk

Reputation: 276

Python Bisection for list of list

If I have the following code...

from bisect import bisect_right
a = [[0, 0], [3, 5], [3,9]]
print(bisect_right(a, [3]))

b = [0, 3, 3]
print(bisect_right(b, 3))

I get the following output

1
3

which is contrary to what I would expect. As far as I understand, Python should use the first element of each list in a to determine the ordering. Then it follows, according to the documentation the first output should be 3 instead of 1 since

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.

It seems to be correct in the second case. Why is it printing 1 in the first case?

Thanks in advance.

Upvotes: 0

Views: 223

Answers (2)

Mad Physicist
Mad Physicist

Reputation: 114320

Python uses lexicographical ordering for sequences. You can imagine the list elements as the characters in a string. If I asked you for the result of

bisect_right(['a', 'ba', 'bb'], 'b')

you would immediately tell me 1, not 3. Obviously 'b' < 'ba'. The same thing applies to lists, whether ['b'] < ['b', 'a'] or [3] < [3, 5].

Upvotes: 2

BatWannaBe
BatWannaBe

Reputation: 4510

The first element in a list isn't the only factor in ordering. When the first elements are equal, the next element is also compared. Since [3] doesn't have a second element, it is deemed lesser.

[3] < [3, 5]
# True

[3, 5] < [3, 9]
# True

[3, 9] < [3, 5]
# False

Upvotes: 2

Related Questions