Es kommt immer darauf an, wie die interne Datenstruktur aussieht.
Es gibt jetzt keinen allgemeingültigen, effizienten Algorithmus aber es gibt mehrere Wege, es effizient zu gestalten. Wenn die Daten unsortiert gespeichert werden, sollte man sich schon überlegen, wie man die Suche so effizient wie möglich gestalten kann.
Eine einfache For-Schleife, die jedes Element sucht, wäre zwar eine Möglichkeit, aber bei sehr großen Listen extremst ineffizient.
Ein effizienter Weg, wäre ein
binärer Suchbaum als Datenstruktur. Ein binärer Suchbaum sorgt dafür, dass bei jedem Suchvorgang immer die Hälfte der Elemente wegfallen, bis eins oder gar keins übrig bleibt. Somit haben wir im schlimmsten Fall, bei einer Million Elemente, maximal 20 Suchvorgänge. Man muss dann lediglich den linken oder rechten Pfad folgen.
Zum Vergleich: Bei einer for-Schleife hätten wir eine Million Suchvorgänge!
Allerdings ist diese Datenstruktur ein wenig komplexer als ein Array mit Elementen, da die Datenstruktur hier dynamisch verwaltet wird. Man muss also selber Speicher allozieren und wieder freigeben.
Aber auch hier liegt ein Vorteil: Es steht immer genügend Speicher zur Verfügung und zwar immer soviel, wie auch gebraucht wird. Arrays haben eine feste Größe und was macht man, wenn man weitere Elemente speichern will, obwohl das Array schon voll ist? Hier muss man immer mühselig abfragen, ob noch Platz ist, wenn ja, speichern und wenn nein, muss neuer Speicher reserviert werden. Diese Abfrage fällt bei dynamischen Listen weg. Oder was passiert, wenn wir ein Array deklarieren, mit Platz für 1000 Elementen, wir aber nur 5 speichern? Dann haben wir unnötigen Speicherplatz verbraucht.
Ein Problem bei den binären Suchbäumen gibt es: Es wird davon ausgegangen, dass die Elemente unsortiert gespeichert werden. Aber was passiert, wenn die Elemente sortiert vorliegen?
Dann haben wir tatsächlich eine
einfach verkettete Liste. Was den Baum ineffizient macht und wir hätten hier auch wieder unsere eine Million Suchvorgänge bei einer Million Elementen.
Um dies zu verhindern, wurde u.a. 1972 eine Erweiterung der binären Suchbäume entwickelt:
Die Schwarz-Rot-Bäume.
Sie sind vom Aufbau nochmal komplexer, da es exakt auf den Aufbau ankommt. Aber hier wird der Baum korrekt ausbalanciert. Egal, wie die Werte gespeichert werden und wir erhalten einen sehr schnellen Suchvorgang.
Der einzige Nachteil bei Bäumen ist, dass wir immer pro Element einen gewissen Overhead haben, da die jeweiligen Zeiger (Ein Wegweiser zu einer Adresszelle im Speicher) mitgespeichert werden muss. Bei Schwarz-Rot-Bäumen muss auch noch zusätzlich die Farbe gespeichert werden.
Aber dieser Overhead lohnt sich, wenn man es sehr schnell haben will.
