Nehmen wir an, ich habe eine sortierte Liste von Floats. Jetzt möchte ich den Index des nächstniedrigeren Artikels eines gegebenen Wertes erhalten. Der übliche For-Loop-Ansatz hat eine Komplexität von O (n). Da die Liste sortiert ist, muss es einen Weg geben, den Index mit O (log n) zu erhalten.
Mein O (n) Ansatz:
%Vor%Gibt es einen Datentyp zur Lösung dieses Problems in O (log n)?
Beste Grüße Sebastian
Wie wäre es mit halbiert ?
%Vor% Sie müssen möglicherweise den Fall eines Suchwerts behandeln, der kleiner oder gleich dem niedrigsten / am weitesten links liegenden Wert in der Liste ist (in diesem Fall index == -1 ).
Je nachdem, welchen Index Sie bei Gleichheit haben möchten, müssen Sie möglicherweise stattdessen bisect_right verwenden.
Sie können eine binäre Suche in einem Array / einer Liste durchführen, um den Index des Objekts zu erhalten, nach dem Sie suchen, und den Index darunter erhalten, um den niedrigeren Eintrag zu erhalten (da es tatsächlich einen niedrigeren Eintrag gibt!) / p>
Siehe: Binäre Suche (Bisection) in Python
Seien Sie vorsichtig, wenn Sie Fließkommazahlen auf Gleichheit prüfen!
Um einen Teil der Frage nach Datentypen zu beantworten: Im Allgemeinen ist der Dateityp der Binärbaum, der am besten geeignet ist, um Dinge in O (log n) -Zeit zu finden (während O (1) bei Einfügungen und Löschungen erhalten bleibt!). Sie können Dinge darin finden, indem Sie eine Reihe von Links-Rechts-Entscheidungen treffen, was sehr analog zu einer binären Suche in einer linearen Liste ist, aber (IMO) etwas konzeptionell intuitiver ist.
Das heißt, von dem, was ich über Python weiß, scheinen Binärbäume nicht in der Standardbibliothek der Sprache zu sein. Für Ihre Anwendung würde es wahrscheinlich keinen Nutzen geben, eine Implementierung nur für diesen Zweck aufzunehmen.
Schließlich können Sie in einer sortierten Liste sowohl die Binärbäume als auch die Binärsuche verwenden, um die Suche um einen Schritt zu verkürzen: Es ist nicht notwendig, nach dem Schlüsselelement zu suchen und dann zu seinem Vorgänger zurückzukehren. Verwenden Sie stattdessen bei jedem Vergleichsschritt so, als ob der Schlüsselwert zu groß wäre. Dies führt dazu, dass Ihre Suche auf dem nächstkleineren Wert endet. Sorgfältig ausgeführt, kann dies auch bei dem von Bart angesprochenen "fast equal floating point value" Problem helfen.
Wenn ich dieses Recht lese, ist das nächst niedrigere Element das erste Element in der Liste, das kleiner oder gleich x ist. Die halbierende Dokumentation zum Suchen nach sortierten Listen bietet folgende Funktion:
%Vor%Tags und Links python