python-3.xbinary-searchbisect

How to write a key function for bisect.bisect_left that compares both the index of two arrays?


I want to write a key function for bisect.bisect_left and my objective is to compare two lists, call one list smaller than the other only if both elements of it are smaller than or equal to the other list's elements.

[x1, y1] should be placed before [x2, y2] only if x1 <= x2 and y1 <= y2.

My objective is to figure out the placement of a point with (x,y) coordinates in the sorted list of rectangles (with each element as (length and breadth) in order to calculate the number of rectangles that point could fall in.

It can be possible that a point cannot be placed at any such index.


Solution

  • You can use a generator expression that iterates over two lists in parallel using zip:

    import bisect
    
    
    class ComparableList:
        def __init__(self, x):
            self.list = x
    
        def __lt__(self, other):
            return all(x <= y for x, y in zip(self.list, other.list if isinstance(other, ComparableList) else other))
    
    
    original_list = [[1, 1], [1, 2], [3, 3], [3, 4]]
    insertion = [2, 2]
    
    print(bisect.bisect_left(original_list, insertion, key=lambda x: ComparableList(x)))
    
    

    This should print

    2