Python bisect with key occures '<' not supported ... error

Question

I'm asking about how to collectly use key function in bisect on Python3.x.

Now I writed code below:

import bisect

if __name__ == '__main__':
    Q = []
    S = [[1, 2], [5, -8], [2, 0]]

    for s in S:
        print(s)
        i = bisect.bisect_reft(Q, s, key = lambda x : x[0] + x[1])
        Q.insert(i, s)
    print(Q)

It occured "'<' not supported between instances of 'list' and 'int'" When I use bisect.insort instead of bisect and insert, it works good.

In my understanding, bisect compare key(item1) and key(item2). But it compare item1 and key(item2) from my code's working.

I'd like to know the reason of error and how to fix it.

Thank you.

Answer 1

Unfortunately, you have to read the fine print:

key specifies a key function of one argument that is used to extract a comparison key from each element in the array. To support searching complex records, the key function is not applied to the x value.

You need to write:

def my_key(x): 
    return x[0] + x[1]

for s in S:
    print(s)
    i = bisect.bisect_left(Q, my_key(s), key=my_key)
    Q.insert(i, s)
print(Q)

I confess this is highly unintuitive and took me by surprise.

[I also fixed your type. bisect_left]