pythonlistsearchbisect

Search for a specific tuple in a list of tuples sorted by their first element?


Say I have a list of tuples like this, where the int is the "id" for this purpose:

records_by_id = [(10, 'bubble1'), (5, 'bubble2'), (4, 'bubble3'), (0, 'bubble4'), (3, 'bubble5'),]

... and I sort this by the first element of the tuple:

records_by_id.sort(key = lambda x: x[0])

... this gives:

[(0, 'bubble4'), (3, 'bubble5'), (4, 'bubble3'), (5, 'bubble2'), (10, 'bubble1'),]

Now, given the number 4, how do I locate the list index of "(4, 'bubble3')"? Obviously these tuples are now sorted by their first element, so a brute force iteration through the list is not ideal. I'm thinking there must be a way of using bisect ... or something similar. Any ideas?


Solution

  • Reuse the sort key for bisecting:

    from bisect import bisect_left
    
    records_by_id = [(10, 'bubble1'), (5, 'bubble2'), (4, 'bubble3'), (0, 'bubble4'), (3, 'bubble5'),]
    
    key = lambda x: x[0]
    records_by_id.sort(key=key)
    
    index = bisect_left(records_by_id, 4, key=key)
    
    print(index)
    

    Attempt This Online!

    If it's possible that the given number doesn't occur, add a check at the end checking whether it actually occurs at the resulting index.