Python: eine sortierte Liste von Tupeln

Question

Nützliche Informationen suchen:

Informationen darüber, wie eine Liste von verschiedenen Datentypen sortieren sehen: How to sort (list/tuple) of lists/tuples?

.. und Informationen darüber, wie ein durchzuführen siehe binäre Suche auf einer sortierten Liste: Binary search (bisection) in Python

Meine Frage:

Wie können Sie die binäre Suche (oder einen anderen Suchalgorithmus für die Protokollierung (n)) auf eine Liste eines bestimmten Datentyps anwenden, wobei der Schlüssel eine innere Komponente des Datentyps selbst ist? Damit die Frage einfach können wir eine Liste von Tupeln als Beispiel:

x = [("a", 1), ("b",2), ("c",3)] 
binary_search(x, "b") # search for "b", should return 1 
# note how we are NOT searching for ("b",2) yet we want ("b",2) returned anyways 

Zur Vereinfachung noch weiter: Wir müssen nur ein einziges Suchergebnis zurückgeben, nicht mehrere, wenn zum Beispiel („b“, 2) und ("b", 3) bestanden beide.

Besser noch:

Wie können wir den folgenden einfachen Code modifizieren, um die obige Operation durchführen?

from bisect import bisect_left 

def binary_search(a, x, lo=0, hi=None): # can't use a to specify default for hi 
    hi = hi if hi is not None else len(a) # hi defaults to len(a) 
    pos = bisect_left(a, x, lo, hi) # find insertion position 
    return (pos if pos != hi and a[pos] == x else -1) # don't walk off the end 

BITTE BEACHTEN: Ich bin nicht für den kompletten Algorithmus selbst suchen. Stattdessen suche ich nach der Anwendung einiger Standardbibliotheken von Python (ish) und/oder anderer Funktionalitäten von Python, so dass ich jederzeit problemlos eine sortierte Liste eines beliebigen Datentyps durchsuchen kann.

Dank

Answer 1

Nutzen Sie wie lexikographische Ordnung beschäftigt sich mit Tupeln ungleicher Länge:

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

speziellen Fällen kann es zweckmäßig sein, eine benutzerdefinierte Sequenz Typ bisect zu füttern:

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') 

Answer 2

Wie wäre es, die Tupelliste in ein Diktat umzuwandeln?

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