Finden Sie das nächste untere Element in einer sortierten Liste

Question

sagen wir, 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 möglich sein, den Index mit O (log n) zu erhalten.

My O (n) Ansatz:

index=0 
for i,value in enumerate(mylist): 
    if value>compareValue: 
     index=i-1 

Gibt es einen Datentyp für dieses Problem in O Lösung (log n)?

freundlichen Grüßen Sebastian

Answer 1

Sie können auf einem Array/Liste eine binäre Suche tun, den Index des Objekts zu erhalten, die Sie suchen und den Index darunter erhalten den unteren Eintrag zu bekommen (vorausgesetzt, dass es ist eigentlich ein niedriger Eintrag!).

Siehe: Binary search (bisection) in Python

Vorsicht beim comparing floating point numbers für Gleichheit!

Answer 2

Um einen Teil der Frage zu Datentypen zu beantworten: In einem allgemeinen Sinn ist der Datentyp, der am besten geeignet ist, 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 konzeptuell intuitiver ist.

Das heißt, von dem, was ich von Python weiß, scheinen Binärbäume nicht in der Standardbibliothek der Sprache zu sein. Für Ihre Anwendung würde es wahrscheinlich keinen Vorteil geben, eine Implementierung nur für diesen Zweck zu integrieren.

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.

Answer 3

Wie wäre es mit bisect?

>>> import bisect 
>>> float_list = [1.0, 1.3, 2.3, 4.5] 
>>> i = bisect.bisect_left(float_list, 2.5) 
>>> index = i - 1 
>>> index 
2 

Sie müssen möglicherweise den Fall eines Suchwert kleiner oder gleich dem niedrigsten/Wert ganz links in der Liste Griff separat (index == -1 in diesem Fall).

Je nachdem, welchen Index Sie bei Gleichheit haben möchten, müssen Sie stattdessen bisect_right verwenden.

Answer 4

Verwenden Sie das Modul bisect. Die Funktion

gibt den richtigen Einfügepunkt für das Element in der Liste zurück, um die sortierte Reihenfolge beizubehalten.

Answer 5

import bisect 

def next_lower_value(values_list, input_value): 
    index= bisect.bisect_left(values_list, input_value) 
    if index == 0: # there's not a "next lower value" 
     raise NotImplementedError # you must decide what to do here 
    else: 
     return values_list[index - 1] 

>>> l= [11, 15, 23, 28, 45, 63, 94] 
>>> next_lower_value(l, 64) 
63 
>>> next_lower_value(l, 63) 
45 
>>> next_lower_value(l, 1000) 
94 
>>> next_lower_value(l, 1) 
Traceback (most recent call last): 
    File "<pyshell#29>", line 1, in <module> 
    next_lower_value(l, 1) 
    File "<pyshell#26>", line 4, in next_lower_value 
    raise NotImplementedError # you must decide what to do here 
NotImplementedError 

Da Sie den Index und nicht den nächstniedrigeren Wert verlangen, ändern Sie die Funktion next_lower_valueindex - 1 statt values_list[index - 1] zurückzukehren.

Answer 6

Wenn ich dieses Recht lese, ist das nächst niedrigere Element das erste Element in der Liste, das kleiner oder gleich x ist. Die bisect documentation for searching sorted lists gibt diese Funktion:

def find_le(a, x): 
    'Find rightmost value less than or equal to x' 
    i = bisect_right(a, x) 
    if i: 
     return a[i-1] 
    raise ValueError