Eine sortierte Liste suchen?

Question

Gibt es Python-Einbauten oder weit verbreitete Python-Bibliotheken, um eine Suche in einer sortierten Reihenfolge durchzuführen?

Answer 1

bisect ist Teil der Standardbibliothek - ist das, wonach Sie suchen?

Answer 2

Es ist erwähnenswert, dass es einige hochwertige Python-Bibliotheken zur Verwaltung einer sortierten Liste gibt, die auch eine schnelle Suche implementieren: sortedcontainers und blist. Die Verwendung dieser hängt natürlich davon ab, wie oft Sie Elemente aus der Liste einfügen/entfernen und suchen müssen. Jedes dieser Module stellt eine Klasse zur Verfügung, die die Elemente effizient in der Sortierreihenfolge verwaltet.

Aus der Dokumentation für SortedList:

L.bisect_left(value) 
    Similar to the bisect module in the standard library, this returns 
    an appropriate index to insert value in L. If value is already present 
    in L, the insertion point will be before (to the left of) any existing 
    entries. 

L.bisect(value) 
    Same as bisect_left. 

L.bisect_right(value) 
    Same as bisect_left, but if value is already present in L, the 
    insertion point will be after (to the right of) any existing entries. 

Beide Implementierungen verwenden binäre Suche den richtigen Index des gegebenen Wert zu finden. Es gibt eine Seite für die Wahl zwischen den beiden Modulen.

Haftungsausschluss: Ich bin der Autor des Sortedcontainers-Moduls.