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. list
s 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 int
s, you'll find the spot where the inner list
has id+1
as the first element. By being shorter than the two-element list
s, 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).