ich habe eine Liste mit mehren tausend Einträgen. Ich muss sehr häufig vergleichen, ob ein Eintrag schon vorhanden ist oder nicht. Zum Suchen verwende ich die binäre Suche. Aber was ist nun die beste Methode, neue Einträge in diese Liste vorzunehmen?
Bisher habe ich bei einem negativen Ergebnis der binären Suche den neuen Eintrag dann einfach mit list.append(neu) angehangen und danach mit list.sort() neusortiert. Da mir die binäre Suche aber doch eigentlich schon die Stelle sagt, an der das neue Element stehen müsste, kann man es doch eigentlich direkt mit list.insert(index,neu) einfügen und ich könnte mir das sortieren sparen. Die Frage ist jetzt, was performanter ist. insert oder append und anschließendem sort?
Mir steht nur Python 2.2 (auf dem Handy) zur Verfügung.
Code: Alles auswählen
#
def binaere_suche(liste, eingabe):
maxindex = maxlen = len(liste) - 1
suche_erfolgreich = False
index = 0
while not suche_erfolgreich and index <= maxindex:
mitte = index + ((maxindex - index)/2)
if liste[mitte] == eingabe:
suche_erfolgreich = True
elif eingabe < liste[mitte]:
maxindex = mitte - 1
else:
index = mitte + 1
if suche_erfolgreich:
return (1,mitte)
else:
if index > maxlen:
mitte +=1
return (0,mitte)