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?
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).