Python bisect with value x is an array of length 1

Question

I'm trying to understand this code:

i = bisect.bisect(self.A, [id + 1]) - 1

Here, the developer passed [id + 1] in the bisect() as x (the target value). In both Python docs and its source code for bisect, I don't see anywhere mentioned that x can be an array of length 1 like that.

The goal of the code is to find in A the value of a tuple that has id or the biggest id in A. For example:

A = [[0, 0], [2, 4]]
id = 1
Output = 0 // Here: 1 isn't in A so return value 0 from id 0 which is the biggest id < input id
A = [[0, 0], [2, 4], [3, 12]]
id = 3
Output = 12 // 3 is in A so return 12

I've tried taking out the ids to try to find the value but my code returns the wrong answer:

A = [[0, 0], [2, 4]]
id = 1
ids = [0, 2]
i = bisect.bisect(ids, id) // return 1 which is correct for bisect but not the expected result
i = bisect.bisect(ids, id + 1) - 1 // still returns 1
i = bisect.bisect_left(ids, id + 1) - 1 // still returns 1

i = bisect.bisect_left(ids, id + 1) - 1 // returns 0

However, bisect_left() will return the wrong answer for:

A = [[0, 0], [2, 4], [3, 12]] 
id = 3
i = bisect.bisect(self.A, [id + 1]) - 1 // returns 12 which is correct
ids = [0, 2, 3]
i = bisect.bisect_left(ids, id + 1) - 1 // returns 4 

So why is the difference? How does passing [x] work?

Answer 1

There's no special case for bisecting with a list as the argument. lists can be compared just like anything else, and the comparison is lexicographic on the elements. So if you search for [id + 1] in a list of two-element list of ints, you'll find the spot where the inner list has id+1 as the first element. By being shorter than the two-element lists, it's always less than anything with an identical first element, so bisect_left will give a consistent placement relative to equal elements, always at the very beginning of the run of equal elements (whereas if you'd passed [id + 1, 0], you'd come after any elements where the second int was negative).