Python: Search A Sorted List Of Tuples

Useful information: For information on how to sort a list of various data types see: How to sort (list/tuple) of lists/tuples? .. and for information on how to perform a binary sea

Solution 1:

Take advantage of how lexicographic ordering deals with tuples of unequal length:

# bisect_right would also work
index = bisect.bisect_left(x, ('b',))

It may sometimes be convenient to feed a custom sequence type to bisect:

class KeyList(object):
    # bisect doesn't accept a key function, so we build the key into our sequence.
    def __init__(self, l, key):
        self.l = l
        self.key = key
    def __len__(self):
        return len(self.l)
    def __getitem__(self, index):
        return self.key(self.l[index])

import operator
# bisect_right would *not* work for this one.
index = bisect.bisect_left(KeyList(x, operator.itemgetter(0)), 'b')

Solution 2:

What about converting the list of tuples to a dict?

>>> d = dict([("a", 1), ("b",2), ("c",3)])
>>> d['b'] # 2