Using bisect in a list of tuples?

Question

I'm trying to figure out how to use bisect in a list of tuples for example

[(3, 1), (2, 2), (5, 6)]

How can I bisect this list according to the [1] in each tuple?

list_dict [(69, 8), (70, 8), ((65, 67), 6)]
tup1,tup2 (69, 8) (70, 8)
list_dict [((65, 67), 6)]
fst, snd ((65, 67),) (6,)

And I'm inserting to bisect

idx = bisect.bisect(fst, tup1[1]+tup2[1])

Which gives me unorderable types: int() < tuple()

Answer 1

In some cases just the simple

bisect(list_of_tuples, (3, None))

will be enough.

Because None will compare less than any integer, this will give you the index of the first tuple starting with at least 3, or len(list_of_tuples) if all of them are smaller than 3. Note that list_of_tuples is sorted.

Answer 2

Check the bottom section of the documentation: http://docs.python.org/3/library/bisect.html. If you want to compare to something else than the element itself, you should create a separate list of so-called keys. In your case a list of ints containing only [1] of the tuple. Use that second list to compute the index with bisect. Then use that to both insert the element into the original (list of tuples) and the key ([1] of the tuple) into the new list of keys (list of ints).

Answer 3

Answers that suggest transforming the input list are defeating the purpose of bisect by converting what should be an O(log n) into an O(n) operation. A better solution is to use a view on the input:

class _list_view:
    def __init__(self, a, key):
        self.a = a
        self.key = key

    def __getitem__(self, index):
        return self.key(self.a[index])


def bisect_left(a, x, lo=0, hi=None, key=id):
    from bisect import bisect_left
    hi = hi or len(a)
    if key == id:
        return bisect_left(a, x, lo, hi)
    return bisect_left(_list_view(a, key), x, lo, hi)

Answer 4

Since version 3.10 you can pass a key to bisect methods to specify the index you want to search on - more info here:

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.

import bisect
tuple_list = [(4, 117), (10, 129), (30, 197)]
# search among first indices - returns 1
bisect.bisect_left(tuple_list, 10, key=lambda i: i[0])
# search among second indices - returns 1
bisect.bisect_left(tuple_list, 129, key=lambda i: i[1])
# 2
bisect.bisect_left(tuple_list, 130, key=lambda i: i[1])

Answer 5

I faced the same issue. I was storing list of (file_id, word_frequency) tuples and wanted to get the list sorted by second element in the tuple which is word_frequency. I did some research and found out how python compares tuples which is describe here https://howtodoinjava.com/python/compare-tuples/.

Essentially it looks at first element of two tuples and takes the smaller one. If the first elements are same then it compares second values an so on.

So what I did was exchanged the elements in tuple (word_frequency, file_id). Now I got my list sorted according to word frequency using bisect.

Hope this helps